Making theory more accesible for everyone

Jeffrey Kluger is the author of a number of books, including Simplexity: Why Simple Things Become Complex (And How Complex Things Can Be Made Simple). Perhaps we can make complexity theory into simplexity theory, which would be great.

Today I wonder why computer science—not just theory—is nowhere to be seen in his recent Time Life book on The Top 100 New Scientific Discoveries of 2010.

The topics Kluger includes, as editor, in this book are all called “Fascinating, Unbelievable, and Mind-Expanding Stories.” That actually is the subtitle of the book. The sections are on Cosmology and Physics and Biology and ${\dots}$, but nothing is called computer science. Nothing is called mathematics either, so perhaps we should not be too upset.

Even worse, many computer science advances are in the book, but they are labeled as contributions of other disciplines.

The Time Book

Kluger really tries to make his pieces accessible. Let’s call them chunks. Here is a sample:

Levitation Achieved—Really

Physics always wants to come out and play. Just when the most technical of sciences become impossibly arcane, it goes goofy on you. That happened in big way when a team of researchers announced in the Journal Nature that they mastered a new way to levitate physical objects ${\dots}$

The title, story and picture are pretty exciting and fun to read. I think we need something like this for theory, and perhaps for computing more generally.

Nuggets

Salil Vadhan to the rescue. He has been working hard for the last few years to create nuggets for NSF. A nugget in the sense of NSF, the National Science Foundation, is by definition a cool picture with a cool description. A nugget should be able to inform non-experts, not be too misleading to experts, and generate excitement. The main use of nuggets by NSF seems to be internal: to help make the case that an area, in this case theory, is making important contributions to their mission.

Salil is the lead on this project, which has been underway since 2008, and he has been helped by many others. The initial organizing committee comprised Bernard Chazelle, Anna Karlin, Richard Ladner, Salil, and myself. See here for details on the project. You will immediately see that contributions have been made by many hard-working theorists. Elaine Park is working on the actual pictures for the project, which may be as important as the words that describe each nugget. The plan is that the nuggets will become posters and go on the walls of CCF—the part of NSF that funds most of theory. Hopefully, the posters will help NSF, and help the entire field. If you have any ideas or wish to help please go to the home site and get involved. Salil would love any additional help.

Here is a sample nugget that is still being worked on:

Computing as a Commodity: Distributed Computing over the Global Internet

Imagine an Internet that automatically and securely carries out complex computational tasks for geographically dispersed users, serves their rich personalized data requests, and provides seamless group communication ${\dots}$

Chunks vs Nuggets

One difference between chunks and nuggets is pretty clear—just recall the titles:

• Levitation Achieved—Really
• Computing as a Commodity: Distributed Computing over the Global Internet

Chunks are written for lay people, for maximum impact, and are fun to read. Nuggets are written for technical people. They do not have anywhere near the impact or the fun factor of a chunk. It seems to me that there are two possible responses.

1. Who cares? Our nuggets are meant to inform technical managers at NSF, and so they should be serious, have real content, and not be fun to read.

Another response is:

2. We care. Perhaps our nuggets should not only inform technical managers at NSF, but should also have the punch of a chunk—OK I could not resist. If our nuggets did look more like chunks there might be several positive outcomes. They might get included in the next Time Book on innovations for 2011. They might be used to reach a much wider audience, which could include other policy makers as well as general lay people.

Potential Chunks?

One answer is that we could create both nuggets and chunks: nuggets go to NSF and chunks are more popular versions of them. Here is an attempt to start to write the nugget “Computing as a Commodity: Distributed Computing over the Global Internet” as a chunk.

Being There Without Being There

Travel is fun, unless your flight is delayed, is crowded as usual, or you fly during a mealtime (do not fill up on those peanuts). Soon we will be able to make much of long-distance travel unnecessary: no more delays, no crowded seats, and no peanuts. Researchers are using the Internet to create an environment where people can work together seamlessly on projects of almost any kind. The only downside is there will be no frequent flyer miles for when you really want to be there—like take a vacation to the beach ${\dots}$

Open Problems

Should we stay with nuggets alone? Or should we start to write chunks too? What do you think?

July 12, 2011 8:57 am

I’m at NSF. We don’t call them nuggets anymore. They are called highlights. These days they are intended to convey to the general public what their investment in NSF is getting them. So in addition to describing, in lay terms, the science that is funded the highlights are also supposed to convey the societal benefits of the research – which we call broader impacts.

So we’re looking more for chunks rather than nuggets.

John

July 12, 2011 9:22 am

PROLOGUE: The Eight-Coloring Riddle

What you hold in your hand,
The intrigue of four-coloring,
You may understand.

Mysteries and riddles,
Around us abound,
Unmitigated intractability
Is not often found.

Consider the Four Color Conjecture,
Poetic simplicity runs deep.
What it has done to mathematicians,
Should make philosophers weep.

The key to that riddle,
May be in the way that we rhyme,
We’ll do it again,
This makes the eighth time.

Checkers and chess,
Boards of Gaussian design.
Try Non-Gaussian arithmetic,
Odd-even all the lines.

Take a look at the algorithm,
That we present here.
Can we prove a variation,
Will four color every plane and sphere?

The Eight-Coloring Algorithm:

1. Pick a country at random. Call it the origin of the x-coordinate. Assign it an x-
coordinate, x=0. For each country that touches the country where x=0, assign it an x-coordinate, x=1. For each country that touches a country assigned x=1, which has not been assigned an x-coordinate, assign it an x-coordinate, x=2. Continue the recursion for all the countries and call it a Recursive Coordinate Assignment. The x-coordinate assigned to a country should be the smallest number of lines that would be crossed traveling from the origin of the x-coordinate to every other country thru all the countries.

2. By definition, a “group” of countries is a set of countries that can be reduced to a single country by erasing all the borders between countries which are members of the set. For each group of countries where x=a, pick a country at random. Call it the origin of the y-coordinate. Assign it a y-coordinate, y=0. Do a Recursive Coordinate Assignment for all the countries in the group where x=a. The y-coordinate assigned to a country should be the smallest number of lines that would be crossed traveling from the origin of the y-coordinate to every country in the group where x=a thru the countries where x=a.

3. For each group of countries where x=a and y=b, pick a country at random. Call it the origin of the z-coordinate. Assign it a z-coordinate, z=0. Do a Recursive Coordinate Assignment of the z-coordinate for all the countries in the group where x=a and y=b. The z-coordinate assigned to a country should be the smallest number of lines that would be crossed traveling from the origin of the z-coordinate to every country in the group thru the group of countries where x=a and y=b.

4. View zero as an even coordinate. If the algorithm has been performed correctly, no two countries with the same sequence of odd-even coordinates will touch and the map will be correctly “colored” with eight non-touching sequences.

And those that we bore.
We’ll show you the score.

Puzzling mysteries thru.
We’ll give you these clues.

The first step, two-colors,
Where three are too much.
The third step can be less random,
So that six never touch.

The impossibility of five,
Makes the three-step reduction to eight.
Count country or group,
Numeric size doesn’t rate.

Be as skeptical as possible,
Draw a map or two.
Match wits with the algorithm,
It’s not easy to do.

Beyond step three,
May be beyond our wit.
The proof is a bit sketchy,
But all the pieces seem to fit.

Back to the work,
Amateurs, I guess,
We paused here to play.

If this work, strikes out,
Useless and/or untrue.
It will be a sad day in Mudville,
But don’t color us blue.

One way or another,
Folks do what they must.
One day, Little Conjecture,
We’ll have a proof that we trust.

Roll over Plato,
Tell Aristotle the news.
You can’t use a computer,
To cure the four-coloring blues.

3. July 12, 2011 9:27 am

I get worried that if we present too many simplified overviews, the missing underlying depth will lead people to the wrong conclusions. Learning just a bit of something complex like mathematics makes it too easy to believe that you really understand it, a lesson I’ve too often failed to heed.

On the other hand, as the sophistication of our knowledge grows, we need more easily digestible pieces that can be passed on from generation to generation. Abstraction is a necessity for accumulating large amounts of knowledge. Our brains aren’t the infinitive resources we like to think they are…

With that in mind, and a sense of how things evolve, I think that the more approaches we take towards higher-level understandings, the better we’ll be in the long run.

July 12, 2011 9:59 am

Key:

The “trick” is to turn random maps into Non-Gaussian Coordinate Systems.

The simplest way to proceed is to draw logic diagrams.

To “see” how the eight coloring algorithm works, perform the following algorithm:

1. Take a clean sheet of paper. In the top middle write the expression: x equals or is less than a-1. Draw a circle around it.

2. In the lower left quadrant, write the expression x=a and y equals or is less than b-1. Draw a circle around it.

3. In the lower right quadrant, write the expression x=a, y=b, and z equals or is less than c-1. Draw a circle around it.

4. In the middle of the page, write the expression x=a, y=b, z=c. Draw a circle around it.

5. Draw a directed line from the middle circle, to each of the other three.

6. Draw a directed line from lower right quadrant circle to lower left quadrant circle and a second directed line to top circle.

7. Draw a directed line from the lower left quadrant circle to the top circle.

Essentially: we have used used the coordinates to divide, slice, and dice the map into mutually exclusive and mutually touching groups.

There can be an indefinite number of countries with the same (x,y,z) coordinates, but no two eah other will touch each other without violating planarity.

If you want to tackle problems on higher genus surfaces, just keep adding coordinates recursively.

July 12, 2011 11:37 am

Short answer: Yes, we should write chunks, not just nuggets, to increase visibility and understanding of computer science in the eyes of the public (which ultimately controls long-term funding trends).

Long answer: These chunks need to have *concrete examples*. This is one of the problems with computer science compared to physics or biology or chemistry. Levitation is concrete, a drug that treats a disease is concrete, but something like “an environment where people can work together seamlessly on projects of almost any kind” is not. What does “seamlessly” really mean, from a layman’s point of view? What will we be able to do that we couldn’t do before? We could use the same sentence to advertise telephone networks (you won’t have to travel anymore, you can just talk on the phone), email, Skype, etc.

Coming up with very concrete examples can be extremely difficult, but I think it is crucial. This is sort of like when a new CEO tells his shareholders that he will “streamline and improve corporate synergy”. The CEO might have a concrete and brilliant plan, but to a random person listening, what the CEO said means nothing, except maybe that people are going to get fired :)

July 12, 2011 9:33 pm

Levitation is very specific. “Researchers are using the Internet to create an environment where people can work together seamlessly on projects of almost any kind” is not at all. This takes away its punch.

You want to make your nuggets/chunks concrete and to do so I think it is best to focus on narrower areas and specific research papers or projects. Doing this also has the advantage that interested laymen can dig a bit deeper and learn about the actual scientists and get their personalities. Don’t underestimate the importance of this human touch.

7. July 13, 2011 1:14 am

The nugget example seems very bad; it sounds like vacuous marketing-speak. And a “commodity” is something that you inherently want to avoid investing in, right?

My attempt at making it more concrete would be like: “Up In the Air — First there were reel-to-reel tapes. Then compact disks. Then music players with computer hard drives. What’s the next media for your music, pictures, and documents? It’s nothing at all. Unseen computers, all around the planet, connected through the air to any device you carry, all the time.”

Or maybe as I thought waiting for the bus today, people watching (reaching a bit here): “Community Everywhere — Did you ever wish we had the power, like ants, you be in communication with everyone in our social circle all the time? Now we do. Omnipresent connections with loved ones, community members, safety experts, wherever you are, all the time. Instant warnings if emergencies arise, from anyone on the scene. Offers of help from those who can provide it the fastest.”

8. July 13, 2011 9:42 am

This week’s XKCD points out that even better than chunks or nuggets would be Computational Complexity fan fiction (C/C-FF). Does C/C-FF exist? Could it? After all … there’s always been an undeniable chemistry between Alice and Bob. :)