Zero-Knowledge Sudoku

Victor has tried and failed to solve the latest Sudoku game and exclaims no solutions exists. His wife Paula has already solved the game. How does Paula convince Victor that a solution exists without giving the solution away?
A Sudoku game is a 9x9 board partially filled out with numbers 1-9.

9

2

3

8

4

1

4

5

6

1

7

6

2

1

9

8

2

5

4

2

9

5

8

3

2

The goal is to fill out the rest of the board with numbers 1-9 such that every row, column and the 3x3 sub-boxes all have exactly one of each digit in them.

1

9

7

6

8

2

3

4

5

6

8

5

3

4

1

9

7

2

4

3

2

7

9

5

8

6

1

4

1

8

7

6

3

2

5

9

5

6

9

8

2

4

7

1

3

2

7

3

5

1

9

6

8

4

9

2

6

5

7

1

8

3

4

4

3

7

2

9

8

1

5

6

1

5

8

3

4

6

9

2

7

Sudoku is an NP problem so Paula and Victor could reduce the problem to graph coloring and use the original zero-knowledge protocol for coloring. Or you can view Sudoku as a graph coloring problem. Here is a way for Paula can do a zero-knowledge proof on Sudoku directly, loosely based on the graph coloring protocol.
Paula goes to a different room than Victor and chooses a random permutation σ of {1,…,9} say σ(1)=2, σ(2)=8, σ(3)=6, σ(4)=5, σ(5)=4, σ(6)=9, σ(7)=1, σ(8)=7 and σ(9)=3. Paula then permutes the solution using σ as such.

2

3

1

9

7

8

6

5

4

9

7

4

6

5

2

3

1

8

5

6

8

1

3

4

7

9

2

5

2

7

1

9

6

8

4

3

4

9

3

7

8

5

1

2

6

8

1

6

4

2

3

9

7

5

3

8

9

4

1

2

7

6

5

5

6

1

8

3

7

2

4

9

2

4

7

6

5

9

3

8

1

Paula then puts each entry into a lockbox (which can be implemented using cryptographic assumptions) and gives the lockboxes to Victor.
Victor can make one of 28 choices.

1. Choose one of the rows.
2. Choose one of the columns.
3. Choose one of the sub-boxes.
4. See the permuted version of the original puzzle.

Paula then unlocks the appropriate boxes. If say Victor picked the third row Paula would reveal

6

5

4

3

1

8

7

9

2

Victor will accept if all of the digits in the row appear exactly once. Note that every possible permutation in the row will occur with equal probability over the choice of σ, so Victor learns nothing about the solution from this question.
If Victor picked the last choice Paula would reveal

3

8

6

7

5

2

5

4

9

2

1

9

8

2

3

7

8

4

5

8

3

4

7

6

8

Victor accepts if this is really a permutation of the original problem. Since the permutation σ is chosen at random again Victor learns nothing about the solution from this question.
Why should Victor now be convinced that a solution exists? If there was no solution, Paula could not find a permutation that causes Victor to accept for all of his 28 choices for the permuted puzzle is just the original puzzle in disguise. If Victor makes his choice at random then he will catch a cheating Paula with probability at least 1/28.
That still gives Paula a possible 27/28 chance of cheating. So repeat the protocol 150 times, each time Paula throws away the unused lock boxes and chooses a new permutation. Paula's chance of cheating in every round is at most (27/28)¹⁵⁰ < 0.5%.
Moni Naor gives a different protocol using scratch-off cards where Paula could never cheat Victor.

Fulkerson Prize

The winners of the 2006 Fulkerson Prize have been announced. The Fulkerson prize is given every three years to up to three papers in discrete mathematics.

• Primes in P, Manindra Agrawal, Neeraj Kayal and Nitin Saxena
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Mark Jerrum, Alistair Sinclair and Eric Vigoda.
• Graph Minors. XX. Wagner's conjecture, Neil Robertson and Paul Seymour.

Great papers all. The Robertson-Seymour Theorem required twenty papers. Roughly it states that any graph property (like planarity) closed under edge contractions and edge and vertex deletions has a finite set of forbidden minors. This result has an interesting consequence that all such properties have a polynomial-time algorithm though there is no known method of constructing the algorithm from the property.

I disagree with Luca and Oded on awards. While theory is a team sport, we do like ways to recognize the very best work and individuals in our field. And awards get us talking about the best work. Even when we don't agree with the winners, the discussions that follow help us understand what we think is important.

By the end of the month we'll know the winners of the Fields Medal and the Nevanlinna prize. The excitement mounts.

Privacy

I have used Gmail extensively as my main email system for a couple of years now. I often get asked about letting Google have access to all my email. Is my email more secure on a machine run by Google or by the University of Chicago? Hint: Which one can my employer read without a court order?

Actually I don't care, I use Gmail because I like the interface and the ability to read my email on any browser on any internet-connected computer.

Computer scientists take as a given that everyone worries about privacy. But in fact, outside of computer scientists and a few other techophobes, most people don't. Google not only has my email but also my calendar and if they ever started Google Money, my financials as well. Nearly every major and most minor transactions I make leave an electronic trace. With the right passwords on the Internet you can see what products I buy, what books I read, what movies I rent. So what?

Best as I can tell worries about privacy come from an inflated notion of self-worth. In reality nobody really cares about your private information. The safeguards we have against privacy, while far from completely secure, are enough to deter people for looking for information that just isn't that valuable. Damage will come from people writing in the open; Something someone is writing in their Myspace account today will come back to haunt them thirty years from now when they run for public office.

I do worry about my information online. I worry that people will could delete my files, assume my identity or steal my assets. However I have the ultimate protection against privacy concerns: If you look very carefully at my email, my calendar, the web pages I visit and the stuff that I buy, you'll truly discover that I'm just a really boring person.

Full Derandomization

What does the complexity world look like if we have hard functions that let us efficiently derandomize? All of the results in this post follow from the following open but reasonable hardness assumption.

There is some language L computable in time 2^O(n) such that for some ε>0, every algorithm A computing L uses 2^εn space for sufficiently large n.

First are the complexity class collapses. As always see the Zoo if some class does not look familiar.

• ZPP = RP = BPP = P
• MA = AM = NP. In particular Graph Isomorphism and all of statistical zero-knowledge lie in NP∩co-NP.
• S₂P = ZPP^NP = BPP^NP = P^NP
• The polynomial-time hierarchy lies in SPP. As a corollary PH ⊆ ⊕P ∩ Mod_kP ∩ C₌P ∩ PP ∩ AWPP

One can also derandomize Valiant-Vazirani. There is a polynomial time procedure that maps a CNF formula φ to a polynomial list of formula ψ_i such that

1. If φ is not satisfiable then all of the ψ_i are not satisfiable.
2. If φ is satisfiable then some ψ_i has exactly one satisfying assignment.

Beyond complexity classes we also get some randomized constructions such as creating Ramsey graphs. In polynomial in n time, we can generate a polynomial list of graphs on n vertices, most of which have no clique or independent set of size 2 log n.

This gives a short list containing many Ramsey graphs. We don't know how to verify a Ramsey graph efficiently so even though we have the short list we don't know how to create a single one. Contrast this to the best known deterministic construction that creates a graph with no clique or independent set of size 2^{(log n)o(1)}.

We also get essentially optimal extractors. Given an distribution D on strings of length n where every string has probability at most 2^-k and O(log n) additional truly random coins we can output a distribution on length k strings very close to uniform. The truly random coins are used both for the seed of the pseudorandom generator to create the extractor and in applying the extractor itself.

One also gets polynomial-time computable universal traversal sequences, a path that hits every vertex on any undirected graph on n nodes. The generator will give a polynomial list of sequences but one can just concatenate those sequences. The hardness assumption above won't put the sequence in log space, though we do believe such log-space computable sequences exist. Reingold's proof that we can decide undirected connectivity in logarithm space does not produce a universal traversal sequence though it does give a related exploration sequence.

There are many more implications of full derandomization including other complexity class inclusions, combinatorial constructions and some applications for resource-bounded Kolmogorov complexity.

On Being Color Blind

In the back of my high school Biology book had a big circle with many smaller circles and I clearly made out the word "color". That was easy I thought until I read the caption

If you see the word "onion" you have normal color vision. If you the word "color" you are red-green color blind.

Being color blind is like living in flatland. You miss a dimension and never notice until someone points it out to you. I grew up making the occasional color mistake but just believing everybody saw green and brown as different shades of the same color.

I have had more official tests that show me fully red-green color blind. I don't see the world in black and white; I don't even have trouble distinguishing red and green. I do see certain color pairs as different shades of the same color: green-brown, blue-purple, red-pink and yellow-orange.

As an undergrad I took a course in computer graphics and they did a demonstration where they showed a colorful picture and then showed three variations where they would turn off one color in each. The instructor said that the original and one of the variations would look the same to a red-green color blind person. Everyone laughed but I went up closely and couldn't tell the two apart.

One day shopping with my wife, she held up two shirts and asked me which one I liked better. They looked identical to me. I claimed she was playing games with me. Now with my knowledge of interactive proofs, I could have tested her: Mix up the shirts behind my back and make her tell me which was which.

My father-in-law is also red-green color blind which means my daughters had a 50% chance of being color blind, a rarity for females. We've tested them and neither is color blind, at least not to the extent that I am.

While color blindness has no cure or fix, it is one of the easiest disabilities to live with. My wife and daughters make sure my clothes match. I have trouble when people give color-coded talks but that doesn't happen often in theoretical computer science. I try to keep colors simple on my own talks and webpages. The Red-Green 3-D glasses don't work for me at all, though the newer polarized 3-D glasses work just fine. I don't usually have trouble at traffic lights but I do have trouble telling blinking red from blinking yellow. If I can't tell from context I just stop, sometimes to the chagrin of the car behind me.

But when I look at art or nature I see one less dimension of colors than most everyone else. I will never know what I am missing.

The Collected Works of Lance Fortnow

In the ancient days of the early '80s when you wanted a copy of a research paper and didn't have it in your library, you sent a stamped self-addressed envelope to one of the authors who would send the paper back to you.

I started graduate school in 1985 as a member of that new-fangled email generation. When I got an email request for a paper, I tried sending a LaTeX file, sometimes getting the response "What am I supposed to do with this? Can't you just send me the paper in the mail?"

But as people became more comfortable with email I got many more email requests for papers, and responding to those requests took some time. When the the web started in the early '90s I set up a page for people to download the papers. I would still get email requests for a while, responding to the request but with a reminder that they could download my papers online. Around 1994, there was a phase shift and I nearly stopped getting any email requests, everyone knew to look for downloads first. Now most researchers put copies of their papers online and shame on those that don't.

I use a now ancient version of bib2html to generate the publications page. It makes for a functional but not very pretty page. I use the same bib file to generate both the webpage and the papers list in my CV.

I tell this story because I made the first major change on my publications page in about ten years. It looks pretty much the same, but I added links in the titles to the official publisher's page for the paper. These pages often give an abstract and if you have permission you can download the "official" version of a paper. If you don't have permission you can still download the unofficial version from my page. The publisher's page also gives you a way to link to an official description of the paper without linking directly to a file, something I like to do when I link to papers in this weblog.

I tried to use DOIs when possible or other permanent links so the links shouldn't go bad. The IEEE and the IEEE Computer Society (publishers of the FOCS and Complexity proceedings) maintain two separate digital libraries with some overlap. When I had the choice I linked to the IEEE-CS version because at the University of Chicago we have access to the IEEE-CS downloads but not the general IEEE.

Many other researchers, for example Salil Vadhan, do far better than me, maintaining their own separate page for each paper and sorting their papers by research area. Those young scientists always showing up their elders.

A Metapost

A German student came up to me during the Complexity conference last week. "The Czechs beat the US in the World Cup"

That game happened a month before. "And the Italians beat the Germans. What is your point?"

"You had said in your weblog that the game would long be forgotten before you came to Prague and I wanted to prove you wrong."

I try to keep my blogger persona separate from my real persona and not talk about the weblog when I have conversations with my colleagues. Occasionally I would start to write something down, "Weblog Fodder" I'd say.

Still others bring up the weblog, usually asking the question about how much time it takes (as opposed to say any comments about the content of the weblog). So people will stop asking me, a typical non-technical post takes me about 15 minutes. The key is to not worry about perfection; people forget the silly or sloppy posts and will be very happy to point out any mistakes I make.

Then there are those who want to watch what they say to me because it might show up in the weblog. I try not to embarrass anyone or reveal personal information, but I do get most of my ideas from regular conversations with people. Anything you say to me is fair game.

Favorite Theorems: The Permanent

June Edition

The permanent of a matrix has a simple form

Perm(A)=Σ_σ a_1&sigma(1)a_2&sigma(2)···a_n&sigma(n)

where A is an n×n matrix, a_ij is the element in the ith row and jth column and the sum is taken over all permutations σ of {1,…,n}.

Very similar to the determinant except without the negations and a 0-1 permanent counts the number of perfect matchings on a bipartite graph. But while we can compute the determinant quickly and easily check if a graph has a perfect matching the permanent turns out to have an apparently much higher complexity.

Leslie Valiant, The Complexity of Computing the Permanent, TCS 1979.

Valiant shows that computing the permanent, even for 0-1 matrices, is #P-complete, i.e., as hard as counting the number of solutions for NP problems.

While an important hardness result in its own right, Valiant's theorem becomes even more important with later work. Toda's theorem implies the permanent is hard for the entire polynomial-time hierarchy. The permanent also has two very important properties:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.

Those two facts, combined with Valiant's and Toda's theorems, helped the permanent play a critical role in the development of interactive proofs and in some derandomization results, most notably Impagliazzo-Wigderson and Impagliazzo-Kabanets.

The Science and Art of Computation

Amir Michail writes

I was wondering if you might comment on the history behind the formation of computer science, and in particular, on the subsequent overwhelming emphasis on implementation (studied via science/math), rather than specification (perhaps better studied as an art?).

One might argue that two fields should have formed, analogous to architecture and engineering say.

Sure, the implementation part is important (e.g., efficiency), but what to implement should be equally important.

Sure, there are a few subfields of computer science where people try to come up with new sorts of applications, but I think this is worthy of much greater emphasis, a different undergraduate program, a different research methodology (perhaps not so "scientific," but more like "art"). Moreover, I suspect that completely different sorts of people would be attracted to this field.

The MIT Media Lab is perhaps the best example of what such a field would look like.

Would you make the same arguments about physics or biology? Computer science is foremost a science and trying to understand the nature of computation has its own beauty just like trying to understand the fundamental building blocks of the universe.

Can one teach "what to implement" any more than an art class can teach "what to paint"? Best for us to teach the theory and tools of computation and then let the world find neat ways to use computers as they already have in countless ways.

Going Home

Today I fly back to Chicago ending my three country European tour. During this Complexity Conference I stepped down from my role as chair of the conference (organizing) committee and leave the conference in the very capable hands of Pierre McKenzie. I truly enjoyed running the conference over the past six years, particularly in working with different program committee and local arrangement chairs each year. It is time for another leader, but I will miss this role in the conference that has been so central in my academic career.

Other notes from the business meeting:

Pavel Pudlak and Eric Allender are the new members of the conference committee taking over for Harry Buhrman and Avi Wigderson ending their three-year terms.

This year we decided to discontinue the Complexity Abstract program. The abstract program let people write up a one page abstract on any of their papers and Bill Gasarch (later Steve Fenner) would collect and distribute electronically before the conference. The conference started program back in the 80's when people who didn't have their papers in the conference wanted a forum to announce their results. But now with the ECCC and the arXiv, we no longer need this program.

The 2007 Meeting will be June 13-16 at FCRC with STOC and other conferences. Peter Bro Miltersen will be PC chair. There will not be a joint session with STOC as we had at previous FCRCs though there will be some coordination in scheduling the talks during both conferences. The 2008 meeting will be at the University of Maryland.

Complexity Day 1

The Complexity Conference got underway yesterday with an invited talk by Pavel Pudlak on the connections of Gödel's work and computational complexity. Kurt Gödel was in 1906 is what is now Brno in the Czech Republic.

The next talk "Polynomial Identity Testing For Depth 3 Circuits" by Neeraj Kayal and Nitin Saxena is the first paper in Complexity history to win both the best paper and best student paper awards. The main result showed how to deterministically check whether an algebraic circuit was identically zero when the circuit has depth 3 with bounded fan-in on the top gate. Their advisor Manindra Agrawal was program committee chair but he did take the proper precautions in the discussions of the awards.

We had a reception last night at the Michna Palace in Prague. One young student remarked how one must be the smartest person in the world to prove new theorems. Not at all true. We have different backgrounds, different strengths, different experiences, different views on complexity that sets a situation where I can prove something that someone else would struggle with while they can prove something I would never find. Even if you have a similar background to someone "smarter than you", they don't have time to work on every problem so you can find good ones to work on your own.

Most of all my advice is to not worry about others and just work on your own. Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun.

Complexity in Prague

I have arrived in Prague for the Conference on Computational Complexity, my favorite conference as you might guess from the name of the weblog. STOC and FOCS get a broader crowd but many of my fellow researchers from the past two decades come to this conference most years and I enjoy talking with them, catching up with research and with life. Just last night I had dinner with Lisa Hellerstein (a COLT person crashing our conference) and Manindra Agrawal, fresh from receiving his Gödel Prize last week at ICALP in Venice.

Blogging will likely be light this week as the conference keeps me busy and I once again have limited Internet access.

One of the students in Chicago had planned to go yesterday to Israel to work for a month with Eldar Fischer at the Technion in Haifa. He postponed his trip, no so much because of the danger, but because getting to Haifa has become very difficult and the University has temporarily closed. The Technion, aka The Israel Institute of Technology, has by far the largest collection of theoretical computer scientists at any single university. Haifa University also has a nice theory group. We sincerely hope the situation resolves itself quickly and they can return to a sense of normalcy, as normal as one gets in that region.

Principles of Problem Solving: A TCS Response

Peter Wegner and Dina Goldin are at it again. The following is from their Viewpoint article Principles of Problem Solving in the July CACM.

Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)—introduced by Turing to help show the limitations of mathematical problem solving—provide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.

In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.

The "Choice Machines" from Turing's paper are just what we now call nondeterministic Turing machines. In Endnote 8 of his paper, Turing showed that the choice machines can be simulated by traditional Turing machines, contradicting Wegner and Goldin's claim that Turing asserted his machines have limited power.

But more importantly Wegner and Goldin misinterpret the Church-Turing thesis. It doesn't try to explain how computation can happen, just that when computation happens it must happen in a way computable by a Turing machine.

I admit the original single-tape Turing machine does not model interaction as Wegner and Goldin state. Nor does the Turing machine model random-access memory, machines that alter their own programs, multiple processors, nondeterministic, probabilistic or quantum computation. But what that single-tape Turing machine can do is simulate the computational processes of all of the above. Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis.

The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.

We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.

Call me a rationalist then as I continue to hold the belief that no matter how complicated the computational model, we can still use the simple Turing machine to capture its power.

Bouncing a Little French Girl

Those who know me well know my addiction to junk food, often referred to as "Lance Food" during my graduate school days. America has its great variety of such culinary delights like Cheesesteaks and Buffalo Chicken Wings but Europeans do very well on their own going well beyond the omnipresent American chains.
 
In Amsterdam I always go for the Uitsmijter (literally "Bouncer", like at a club), basically an open-faced sandwich with fried eggs on top. I usually go for the Rostbief Uitsmijter and the Ham-Kaas version (Ham and Cheese and the Eggs) can really clog those arteries.
But the Uitsmijter is downright healthy compared to the Porto delicacy Francesinha ("Little French Girl"). One starts with a thick slice of bread then add layers of ham, steak and sausage. Cover with another slice of bread and pour melted cheese on top. Then add the fried egg and smother the whole thing in gravy. Right now Porto is having their Festa da Francesinha by the river where restaurants from all over the city come to offer their versions of the Francesinha.
Luis Antunes says "A little bad food is good for stomach every now and then." After eating a Francesinha at lunch today I'm not sure my stomach agrees.

Useful Information

In our sixth Complexitycast live from Portugal, Luis Antunes talks about the Portugal view of theory, research and of course the World Cup. MP3 (13:26, 2.3MB)

Naming Complexity Classes

How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class was not already named and the name has not been used before. The CCNC then puts out a Request for Comments to the community. Once the community responds, sometimes giving other suggestions for the name, the CCNC makes a formal recommendation to the Complexity Governing Council. The Council takes a final vote on the name.

If only we were so organized. Complexity classes get their name usually from the authors who invent them or occasionally by a later paper if the first paper didn't name the class or gave it an unmemorable name. Too often researchers will give a temporary name so they can work with a class and then keep that name out of laziness. Maybe I've been guilty of this a few times myself.

I could write several posts on badly named complexity classes. For now let me mention two important ones.

• NP for Nondeterministic Polynomial Time. But "nondeterministic" is not very descriptive. Logically ∃P would be better or PV for Polynomially Verifiable.
• PP for Probabilistic Polynomial Time. Since the error is not bounded away from one-half, the class is not a useful characterization of probabilistic computation. A better name would be Majority-P or just MP. BPP would then get the proper name PP and BQP would be just QP.

Someone asked me how to get their class into the Complexity Zoo. You can submit a proposal to the CCNC or just realize the Zoo is now a wiki and edit it yourself.

Definitions of Advice

When Karp and Lipton showed that if NP had polynomial-size circuits the polynomial-time hierarchy collapses, they also give a general definition of nonuniform complexity.

Let C be a class of languages and F be a set of functions. The class C/F is the set of all languages L such that there exists an A in C and an arbitrary f that maps n to strings with |f(n)| in F such that x is in L ⇔ (x,f(|x|)) is in A

Seems natural but this definition has given complexity theorists headaches for many years. The definition works fine for the applications in the Karp-Lipton paper, but it loses the semantic meaning of complexity classes in general.

In particular consider (NP∩co-NP)/poly. We need an A in NP∩co-NP for the definition above, but note that means we need two NP machines that accept complementary languages even for all possible advice strings, not just the correct one. In our toolkit paper we give a relativized world where NP/1∩co-NP/1 is not contained in (NP∩co-NP)/poly. We don't even know if (NP/poly)∩co-NP is contained in (NP∩co-NP)/poly.

At least we can use the terminology NP/poly∩co-NP/poly to nicely capture the class we want. For other classes like BPP/log we have no such clean notation. Once could make some new notation (someone suggested C//F) but instead we usually just state early on that we are not using the official Karp-Lipton terminology and only require the BPP behavior for correct advice.

Karp and Lipton did nothing wrong. They use a very natural definition that works for their purposes. Unfortunately the natural definition does not match the natural interpretation for all classes and will continue to confuse inexperienced complexity theorists for years to come.

On to Portugal

At noon today, as I was checking into my flight to Porto, Heathrow Airport went quiet, part of a nationwide two-minute memorial for the London bombing victims of a year ago. Machines were turned off and everyone stopped talking and just contemplated. The silence was deafening.

So starts the second leg of my journey, a visit to colleague Luis Antunes. As a commenter mentioned I am in Europe but not going to ICALP next week in Venice despite having a paper there. I greatly enjoy going to conferences and workshops but find them quite exhausting and going to three meetings in a row is more, especially with the large and broad ICALP in the middle is more than I can handle. For those in Venice, enjoy the conference and good luck to Italy in the WC final. Afterwards, come on up to Prague for Complexity.

At the workshop in Bristol, the projector was a bit dim and we had some problems reading some colors, green on the white background and red on a black background. This led to a heated discussion on what backgrounds to use. Harry Buhrman argues for white, as one can see the text best. Any background color can work, as long as you don't use too many different colors for text and carefully choose contrasting colors. Though I find any plain color, especially white, a bit boring. I typically use one of the Powerpoint defaults, which Microsoft has designed to both look pleasant and have good readability.

Complexity and Randomness

The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexity (the rest of us). For example Colin McDiarmid talked about the maximum degree of a random planar graph (Θ(log n)) and Mark Jerrum on Monte Carlo mixing methods, in addition to Irit Dinur on her PCP proof, Oded Goldreich on pseudorandomness and coming up Luca Trevisan on Gowers uniformity and Vijay Vazirani on markets.

I don't go to England much because they don't have many researchers in computational complexity, so I get a rare chance to talk to many of the researchers in this area. These workshops give us a chance for us to tell them about the latest in complexity and I can learn about areas I don't keep up with as much as I should.

Leslie Ann Goldberg gave a neat talk on the hardness of estimating the Tutte polynomial of graphs on a variety of points. I never really learned about the Tutte polynomial; it has some cool properties that for various parameters can count properties of graphs such as number of connected components. Goldberg and Mark Jerrum showed some of the approximations are #P-hard, that is hard for counting solutions of NP problems. We rarely see #P-hardness for approximating as all #P problems can be approximated probabilistically with an NP oracle. The Tutte polynomial is harder to approximate on some negative values because of the cancellations given by negative terms.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

A Super Addiction

New superhero movies like Superman Returns and X-Men: The Last Stand remind me of my one time comic book addiction. As a child, I liked to read superhero comics but they had simple stories of saving the world. As I grew up the stories became less interesting and I stopped reading them. In my senior year of college I had a friend who collected comic books and convinced me to start reading them again as the stories have added some sophistication to them. During my last summer before I went to grad school I read through much of his collection. In my first few years of graduate schools I continued to reach comics voraciously and at one point I used a mail-order service to get 25-30 comic books a month.

At some point I realized that I read the books not so much for enjoyment but to finish before the next month's batch arrived. So I went cold turkey, I stopped reading comics and never went back.

However I had gotten my apartment mate hooked and he decided to take over my subscription. Several years later, this would be the mid-90's, the two of us were walking around and entered a comic book store for old times sake. I saw a rack of new releases and we had a conversation that went something like this.

Me: There's Batman, I thought he was paralyzed.
AM: He got better.
Me: I heard Superman was dead.
AM: He got better too.
Me: And the Flash? I remember when he died.
AM: That's Kid Flash all grown up.
Me: At least Wonder Woman hasn't changed.
AM: Actually that's her mother.

The Chicago Tribune just ran an editorial on Spiderman revealing his identity to the world. No worries, in due time the world will forget.

FOCS Accepts and a Movie

The list of accepted papers for FOCS 2006 has been posted. Since I was on the program committee I won't comment on the papers or the process.

So instead I offer to you this short movie (16 MB, 3:14) using soccer to explain Euclid's theorem that there are infinitely many prime numbers. Part of a new British project science.tv.

Finding a Mate

A female professor once told a story of a student who asked her out on a date. After she politely declined, the student asked her if she could be his advisor. Apparently it is harder to find a spouse than to get a Ph.D.

Which brings me to a question asked by a commenter on my Two Body post: How is a CS grad student to find love?

I get asked this question surprisingly often, even though I have been out of "the game" for nearly two decades. My best advice: Find some activity you like and join a club on or off campus that matches that activity. For example, concert band, contra dancing, running, skiing, sailing, etc. You'll meet other lonely people who share at least one interest with you.

I was never good at bars, clubs and blind dates. People like us don't always make a good first impression; that's why it's best to have an opportunity to make friends over time before asking someone out.

I missed the whole on-line dating scene. I have known some people who have had great success with them and others who haven't. Sunday the Chicago Tribune highlighted a new dating site Geek2Geek. Only for the desperate.

Does it matter whether you date an academic or not? Not really, just find the right person for you. Making a two-body problem is often harder than solving it.

FREE REPRINTS

Bill Gasarch is giving away free copies of one of our papers. Get them while they last.

I recently got in the postal mail REPRINTS of a recently published article of mine. This used to be standard—when an article was published you got 50 free copies. Less and less journals do this now.

Are reprints needed anymore?

NO: With everything online nowadays anyone who wants to find or read your article can.

YES: When someone visits you in your office its nice to be able to give them a copy without having to print it out. Also, when I went up for Tenure and Full Prof, I was asked for 14 copies of every article I ever wrote, so it was good to have the preprints around. (some went to my letter writers, which makes sense, some went to the committee deciding my case, which makes less sense, some went to the dean, provost, and for all I know the governor of Maryland, which makes no sense. Well maybe its okay–the governor has a Ph.D. in Mathematics–it was on Recursive Algebraic Topology. I am, of course, kidding–there is no such field.)

Even before the electronic age I never used reprints much (except when I went up for promotion). And the last few times I've written a letter for promotion I was NOT given the set of papers (NOTE: It would have been an appreciated courtesy if they had).

The article A Tight Lower Bound for Restricted PIR Protocols by Beigel, Fortnow and Gasarch (Computational Complexity, Vol 15, No 1, 2006, 82-91) can be YOURS if you send a Self-Addressed Stamped Envelope to

William Gasarch
Dept of Computer Science
University of Maryland
College Park, MD 20742
USA

(I would bet $5.00 I won't get any takers, except that someone may take the bet and request a copy, thus gaining $4.61)

Favorite Theorems: Probabilistic Complexity

May Edition

After we saw several randomized algorithms for primality we needed a way to classify and analyze the power of probabilistic computation. The power of computational complexity comes from not just studying old models of computation but taking new ones and finding ways to analyze their computational power as well.

Computational Complexity of Probabilistic Turing Machines, John Gill, STOC 1974, SICOMP 1977.  A Complexity Theoretic Approach to Randomness, Michael Sipser, STOC 1983.
Gill gave a formal definition of a probabilistic Turing machine and defined the basic classes, PP, BPP, RP (which Gill called VPP) and ZPP and showed the basic relationships between them.
Sipser's main result showed the BPP is contained in the fourth level of the polynomial-time hierarchy and the paper also includes Gács improvement putting BPP in Σ₂∩Π₂. More importantly Sipser introduced new techniques into the complexity theorists' toolbox including

• A new resource-bounded Kolmogorov distinguishing complexity, and
• Using Carter-Wegman hash functions to focus randomness. Perhaps the first extractor.

Sipser's tools go on to play an important role in the complexity of Arthur-Merlin games, graph isomorphism, statistical zero-knowledge and other areas of complexity. But perhaps most importantly Sipser showed you can apply the tools of complexity to really understand the power a new model of computation, the probabilistic machine. How about that newer model of a quantum computer? Bernstein and Vazirani's paper plays the Gill role, in formalizing efficient quantum computation and definining the basic classes like BQP. But while we have had some limited success in understanding the computational complexity of BQP, not only do we not know whether BQP is contained in the polynomial-hierarchy we have not yet developed great tools for understanding "quantumness" the way Sipser has shown we can do for randomness.

Campus Maps

As an academic I can't count how many different college campuses I have visited. Most US universities produce beautiful glossy maps to make it easy to navigate to and around the university but you can't get one of these maps unless someone mails you a copy. So I go to the university's website and can usually find a page of maps.

The University of Wisconsin map page has a beautiful flash version of their campus map. Someone put considerable time to design such a completely useless map. What am I supposed to do, walk around campus with my laptop open to figure my way around? Wisconsin also has a PDF version of their map but when printed the type is so small the map is also useless. Admittedly Chicago does not do maps much better.

The glossy maps are typically much larger than the usual printer page, but still universities can do better than just creating PDFs of shrunken versions of their usual map. Princeton, has their useless interactive map, but their printed map does a nicer job with a second page having a building directory very useful with a duplex printer.

Some day we will carry portable GPS devices which when we visit a campus will download building information and guide us to where we want to go. Until that day universities should take the effort they use to create fancy interactive maps and instead focus on producing a "print and go" map designed specifically for standard letter-size paper.

The Two-Body Problem

Many professional couples can have problems finding jobs in the same city, but for academics the problem magnifies. Even big cities will have only a small number of computer science faculty positions in major research universities and so try to imagine finding two such jobs. This quandary has a name that started as a joke, but no one laughs at trying to solve their Two-Body Problem.

Finding two open positions in the same department and often in the same area (like theory) can be particularly challenging as departments have a limited number of positions available each year. Still a department can often obtain one or two faculty members they might usually lose to a stronger school by going out of the way to solve a two-body problem.

Two-body problems become even more difficult when one member of the couple is considerably stronger than the other, or they are at different stages of their academic careers. In the latter case the older one might have a tenure-track position and then have to go on the job market again to solve their two-body problem. Even if they eventually do land tenure-track jobs at the same department, they will come up for tenure in different years adding more instability.

How about two academics in different fields? Some universities will go out of their way to accommodate such couples, with a dean or provost encouraging one department to hire in order to help strengthen the other department. Many other universities won't try as hard.

Finally are the couples with one academic and a non-academic professional that also has limited geographical jobs opportunities. Here a university can't help at all, one just needs to get lucky.

By US law, one cannot ask a candidate about the two-body problem when they interview, and if they don't mention it one cannot take it into consideration during the hiring process. Nevertheless you should tell the department about your situation. Universities often have ways of solving two-body problems and letting them know about it ahead of time will give them more time to make the right opportunities available.

In the end most two-body problems do get solved, though not always at the place as good as where they might have received a position on their own.

The H-Number

Thomas Schwentick sends me a link to an h-number calculator maintained by Michael Schwartzbach. Jorge Hirsch developed the h-number or h-index as a measure of the scientific output of a researcher.

A scientist has index h if h of his/her N_p papers have at least h citations each, and the other (N_p - h) papers have no more than h citations each.

The h-index discounts researchers who have one or two highly cited articles or books, or those researchers who just churn out mediocre papers.

There are loads of problems with the h-index. Google scholar and other citations counters are inaccurate because of trouble parsing and disambiguating papers. Citation counts do not accurately measure the quality of the paper—a paper that opens a field will get many more citations than a paper that closes it. The h-index rewards fads and cliques who always cite each others work. The h-index gives greater weights to more senior scientists and doesn't separate those who had good early careers from those still going strong.

Having said that we do love to compare ourselves with our colleagues in any way possible. An automated calculator does not work well for even mildly common names but it works great for "Fortnow" and while my h-index of 23 does not put me among the h-number elite, I'll take it.

EC

This week I'm attending EC '06, The 7th ACM Conference on Electronic Commerce in Ann Arbor. The name does not completely fit the conference which focuses mostly on computer science issues in economic models (e.g. computing Nash Equilibria) and economic question related to computer science (e.g. Internet-related auctions, economic mechanisms that solve algorithmic problems). The conference draws a mostly computer science crowd from both the theory and AI communities. Not many economists and most of those from business schools. Some industry folk come but mostly CS researchers from the big internet companies.

So what is a nice complexity theorist like myself doing at a conference like this? I study the power of efficient models of computation and what is an economic market but just another model of computation.

This year's conference had a big emphasis on sponsored search auctions, those keywords you see on the right side of search results. Yahoo, Google and recently Microsoft all run various auction scheme where companies bid on keywords like "mp3 players." Finding the right models, bidding mechanisms and equilibria for these auctions continue to challenge researchers. EC had four submitted talks, an invited talk, a workshop including a panel, and a competition all on sponsored search.

The conference had no overhead projector, white or blackboards. A laptop powered every talk at EC, the first time I've seen that at any conference. However they still had paper proceedings though did talk about possibly eliminating them at future conferences.

EC broke their attendance records with 172 participants who came to the conference and/or one of the workshops. Next year EC will be at FCRC along with STOC, Complexity and many other conferences.

Incomprehensible implies Boring?

Lawrence Downes writes a New York Times opinion Edison, Unplugged talking about the beauty of listening to music recorded in the 20's and 30's on a cylinder.

And there is another pleasure, too. It's the warmth of the technology. There are surely downloadable versions of "True Blue Lou." But unlike the MP3, whose magic is incomprehensible and thus boring, the wax cylinder is viscerally miraculous. It's staggering to think that lungs and plucked strings could vibrate the air, wiggle a stylus and capture a song for 100 years on a fragile thing that looks like a toilet paper roll. Compared with the iPod, it's a lot more human, a lot more accessible, a lot easier to love.

Downes has it backwards. The cylinder technology is very simple and provides a mediocre reproduction of the original music. Meanwhile the MP3 and other compression schemes use beautiful computer science ideas to make a strong digital copy, easily produced and portable, superior to cylinders in every way.

Luckily Downes is the outlier. He can enjoy scratchy music on his "toilet paper roll" while the rest of us enjoy music that sounds like the original on devices we can carry in our pocket, even if most people don't understand the details of technology involved.

EC, PCs and the WC

Fresh off a PC (Program Committee) meeting in NJ (no tellsies), I drove from IL to MI for EC where I was also on the PC. First I spent the day at TTI with lunch at the GSB to watch the USA at the WC. Thankfully by the time I get to CCC that game will long be forgotten.

Time-Travel Circuits

From Computing Like Gods by Jörn Grote

Time travel circuits had been in the first stages of development, but even then it was clear that we had cracked NP complexity. Before TTCs, solving computational problems from the NP-class in polynomial time was like finding the holy grail. And then we got TTCs. They utilized extremely small wormholes, were one opening had been accelerated near the speed of light.

Computers with time travel circuits could easily solve NP-complex problems in polynomial time, but the limit was actually PSPACE. Time travel was characterized by the computational complexity class of PSPACE, a class of problems that was either bigger or at least as big as the NP class.

When the news were out that they had TTCs, most people had no idea what it meant. I can still remember the headlines TIME TRAVEL IS REAL, WE CAN GO BACK, KILL YOUR GRANDFATHER. Naturally all these articles omitted the fact what we really could do with TTCs. It was cheap and easy to create the extremely small wormholes, but bigger ones grew unstable with rising size. The crater where once had been Calcutta tells you that they had found the limit and surpassed it.

Can Settling P vs. NP Get You Sued?

A reader Osias asks

About purported P vs NP solutions…I was wondering what if you, sooner or later, lets say, 10 years from now, solve yourself the P vs NP question. Can those authors sue you, claiming they have solved and you "stole" it from them?

I am most worried about myself too. Cause I am actually reading those papers from them and contributing to a wiki that analyze them. What if those guys decide to sue me? Can they?

I view this question as an extreme hypothetical. I don't expect either you or I will settle the P versus NP problem nor do I believe any of the papers posted on the wiki will play any significant role in the eventual solution.

We rarely see lawsuits in academics and then only when large sums of money are involved, for example patent rights based on research. The Clay Mathematics Institute Millenium Problems do provide a significant sum of prize money but even in the scenario you outline above, the suit would not be against you but instead the Institute for not recognizing the earlier work.

If I write a paper and later learn of some work that overlaps my paper, I will mention this other work even if I was unaware of it at the time of my research. I could imagine a scenario where I don't believe a paper has any connection to my research and the authors of that paper decided to sue me to acknowledge their perceived contributions. In such a scenario I would not be bullied and hold my ground, though not before consulting the university's lawyers.

On a related note, Luca reports on the status of the Poincaré conjecture, likely to be the first Millenium Problem prize awarded by the Clay Math Institute.

Funding Committee Report

At the STOC Business Meeting Richard Karp gave a report from the SIGACT Funding Committee.

Why does TCS [Theoretical Computer Science] have meager funding and little influence with funding agencies?

A possible answer: Unlike the physicists we have no tradition of leadership within the CS community, setting community goals, and advising, serving and lobbying the funding agencies and congress. For physicists this is a normal responsibility and it should be for us as well.

Ways to get involved include

• Write popular articles.
• Contribute short articles for the SIGACT website.
• Serve on NSF panels and as program directors.
• Provide research nuggets to NSF.
• Advise the committee.

The committee suggested two cross-cutting initiatives, Theory of Networked Computing and Computer Science as a Lens for Science.

Theory of Networked Computing will bring TCS into the NSF GENI Initiative. ToNC has already had some influence in the development of the Scientific Foundations for Internet's Next Generation (SING) area of the recent Theoretical Foundations solicitation.

Computer Science as a Lens for Science promotes algorithms as the language of science in many different disciplines including

• Quantum Computing
• Statistical Physics—Phase Transitions
• Algorithmic Economics and Game Theory
• Computational Biology

Most of all the committee wants community action to help in promoting and supporting TCS.

The Funniest Computer Science Joke Ever

My kids watched one of the Disney Channel sitcoms and I caught the following exchange:

Teacher: Do you want to hear the funniest computer science joke ever?
Student: Sure

Customer: My computer crashes every time I press enter.
Tech Guy: So don't press enter.

Teacher: Now wasn't that the funniest computer science joke ever?
Student: Yes it was.

Not so funny. But also nothing to do with computer science. No wonder my kids sometimes think I fix computers for a living.

The May 1 Deadline

In 1964 the Association of American Universities passed the following resolution setting a May 1 deadline for hiring away faculty from other institutions.

The sharp increase in the demand for teacher-scholars of high talent arising from our growing national needs in both instruction and research is now pressing against a limited supply of such talent in many disciplines. To assure the highest possible effect in each university in producing high talent to meet future national needs, sound and orderly planning will be required. When late and sudden, induced departures of personnel assigned to provide instruction to lead in research in one institution may well do more to impair the effectiveness of that institution than is justified by the gain to the institution extending the offer. This is particularly true at the level of tenure appointments where the institution has declared its willingness to undertake a continuing obligation and where there are most likely to be continuing obligations by the faculty member to graduate students and colleagues.

Therefore we consider it incumbent upon the administrations of both the prospective and current institutions of employment to call the attention of the individual faculty member to these obligations when employment changes, not accepted before May 1 for the immediately ensuing academic year, are under consideration. We believe that a responsible approach for both the institutions and the faculty members would be to consider offers made or pending on May 1, or thereafter, to be effective normally only after the intervention of an academic year.

In practice we are strongly discouraged from making such offers after May 1 but if say Harvard wants to hire away a professor from Yale after May 1 for the following academic year, the provost of Harvard makes a request to the provost of Yale and such requests are almost always granted.

Most fields finish up hiring early in the spring and the May 1 deadline reasonably blocks some last minute shuffles. But as the computer science hiring season often goes into June and junior and senior hires often compete for the same slot the May 1 deadline can create havoc in the CS recruiting process.

The high-demand low-supply of faculty in 1964 no longer holds true today. We need to reconsider whether a one-day-fits-all deadline really applies in today's diverse academic hiring environment.

Beauty and the Bee

Last night my daughters and I watched a New Jersey girl win the National Spelling Bee. The final three contestants were all females though my kids were rooting for the boy from Illinois.

Championship spelling requires considerable memorization as you'd expect but it has a mathematical aspect as well. One needs to know how to put together words using very specific rules that depend often on the word's origins, which the spellers can ask about.

A major network (ABC) broadcasted the spelling bee for the first time. ABC once televised the Miss America Pageant, which has since moved to a small cable station because of lack of viewer interest. Amazing to see Beauty lose to the Bee.

Research with Colleagues Visiting for a Short Time

Another guest post by Bill Gasarch

A colleague is going to visit for a short time and you want to get some research done. When does this work? When does this not work? How to you define `work' anyway? Some advice.

1. Have a well defined topic that at least one of you is knowledgeable about.
2. Have complimentary strengths. Or, more accurately, make sure that several strengths are covered (e.g., one knows Algebra, one knows Geometry, so you can do research in Algebraic Geometry. Well, maybe not...) (Better example: one is a knowledgeable about widgets, and one is clever with widgets.)
3. Don't chit-chat or socialize that much, OR at least have it be during a well defined time. For example AT SCHOOL mostly talk about research. AT HOME (if the visitor is staying at your house) socialize. For this reason, having the visitor at your house is a good idea so long as it makes sense logistically and is okay with the spouse.
4. Avoid long big lunches. You feel sluggish afterwards.
5. Right after you've proven something new you are excited about it. Write it up SOON, while you are still excited. For work with visiting colleagues, make sure that ONE of you is assigned to get out the first draft. (This is true of research in general.)
6. How long to stay? Too long can be bad since then there is the temptation to put things off. About a week is good. If someone is visiting for a semester than this is a whole different story, which someone else may blog on.
7. One goal of a collaboration working is that a paper is produced. Other goals could be that you both learn something you didn't know before.

Dispersing Ramsey Graphs

Perhaps the very first example one sees of the probabilistic method: Show there exists a graph on n vertices with no clique or independent set of size k = 2log n. Simply pick the graph at random. For any set S of k vertices the probability that the graph restricted to S will be a clique or independent set is at most p=2^{-(k choose 2)}/2. The probability that any subset S is a clique or independent is at most p times (n choose k) which is less than one for k = 2log n. So there must be some graph with no clique or independent set of size k.

Actually constructing such a Ramsey graph is another story. You can create the graph in quasipolynomial (2^{poly log n}) time using standard derandomization techniques. In 1981, Frankl and Wilson had a polynomial-time construction of a graph that had no clique or independent sets of size 2^{(log n log log n)1/2}. That bound stood until the recent STOC paper by Barak, Rao, Shaltiel and Wigderson creating a graph with no clique or independent set of size 2^{(log n)o(1)}.

Barak et. al. were not trying to create Ramsey graphs, rather to create randomness dispersers for two independent weakly random sources. As a bonus they improved the Frankl-Wilson bound giving yet another example where proving one kind of theorem in complexity gives an exciting result in an apparently unrelated area.

The South Has Risen

Who would have thought the next theoretical computer science powerhouse would have come from Atlanta? Georgia Tech this year has hired Santosh Vempala and Adam and Yael Tauman Kalai into an already amazing theory group. In the past few years Georgia Tech has gone from a good theory program to one of the largest and strongest in the country. How did they accomplish that feat? Seeing potential where others haven't, solving two-body problems both inside and outside the department and most importantly having the resources to go after opportunities when they occur. Alas two of their recent hires came at the expense of Chicago/TTI but hey, all's fair in love, war and recruiting.

It's not like other departments have stopped hiring in theory. In the past two hiring years alone several schools have hired junior theorists including Carnegie-Mellon, Cornell, Michigan, MIT Math, Penn State, Rochester, Stanford, Washington and Wisconsin. Many universities realize that in order to have a strong CS department one needs a strong theory group and in order to improve or even maintain strength in theory one needs strong young talent.

Talking to Publishers

A few publishers showed their wares at STOC. This is a good opportunity to talk them about book ideas or about publisher's policies and how they operate. You can also get some good books at a discounted price; I picked up J. Michael Steele's The Cauchy-Schwarz Master Class from Cambridge University Press based on a recommendation.

I had a lengthy conversation with Sweitze Roffel, who took over Chris Leonard's position as publishing editor of the Elsevier theory journals. Sweitze is quite aware of the negative perception of Elsevier in the theory community and wants to talk to the community about their concerns. So talk to him at conferences or send him email and tell him your concerns about Elsevier's policies. A couple of nuggets.

• Sweitze will move the offices for his journals from Amsterdam to New York to emphasize the global nature of Elsevier and be closer to editors.
• Elsevier has an arrangement with Microsoft's Academic Search but negotiations with Google Scholar are going slowly because of Google's "secretive" policies.
• Elsevier plans to give contributors (editors, referees, authors) access to their Scopus system. Elsevier also has their own free academic search site Scirus.
• The free access experiment of Information and Computation continues.
• Elsevier is exploring starting their own version of Springer's Lecture Notes in Computer Science series and also a Review journal.

I also talked to Lauren Cowles, an editor for Cambridge University Press who wrote a good comment on a publisher's view of putting books on the web. She pointed out Victor Shoup's A Computational Introduction to Number Theory and Algebra is available for purchase and also freely available online.

Flying American

A commenter asked about the Fly America Act that requires, with few exceptions, that when traveling abroad on US money, such as an NSF grant, one must use a US-based carrier. This silly protectionist law just supports American airlines with tax-payer dollars and in the end wastes both money and time. Not only should I be able to fly a foreign carrier to other countries I should even be able to fly a foreign carrier between US cities.

As a practical matter the Act is more a nuisance than a serious problem. US carriers have an extensive collection of foreign routes, you can fly most foreign flights via a US-airline codeshare, and in a jam one could launder some grant money to a non-grant account and then use non-grant money to fly the foreign carrier. Not that I ever have, ever would or ever condone taking the last action.

Thoughts from STOC

I don't go to many talks at STOC, I prefer hanging out in the hallways and talking with other attendees. But the best talk I saw so far was the first, Atri Rudra gave an easy to follow overview of a his paper Explicit Capacity-Achieving List-Decodable Codes with Guruswami. Both student paper award winners also gave nice overviews of their technical results. Much better than trying to wow us with complicated formulas.

What were the folks in the hallways talking about? Worry about funding in the short term but cautious optimism a few years down the line. Some optimism on employment; many good places hired in theory this year and most students found postdoc, faculty or industrial positions. I didn't see many students scrambling for jobs. Last time STOC was in Seattle (1989) I was one of those scramblers.

Prabhakar Raghavan, a theorist who now heads Yahoo! Research, gave the first invited talk about some mathematical questions related to Yahoo. Prabhakar spent a considerable part of his talk on sponsored search, the bidding and ranking mechanisms for those who pay to be listed right of the search results. Yahoo currently uses a variant of second-price auctions that is non-truth telling and has some other flaws but is simple enough for people to understand how much they will pay. Google on the other hand use more complicated schemes with nicer properties but most if not all of its users don't really understand the bidding mechanism.

Russell Impagliazzo gave the other invited talk on pseudorandomness, his title slide containing a joke only my generation would get.

Let's secretly replace Al's coffee cup of random bits with pseudorandom bits and see if he notices.

Russell's take-home message: Randomness does not help in algorithms but we can't prove it doesn't help until the circuit complexity people (like Russell) get on the ball and prove some good lower bounds.

On a personal note, today I have lived as long as my father. Puts a real perspective on life.

STOC Business Meeting

Howdy from Seattle. Here's some highlights from the STOC business meeting.

78 papers accepted out of a record 288 submissions.

There were 275 registrants including 109 students. Rooms at the conference hotel ran out slightly before deadline and the organizers scrambled to find rooms at a nearby hotel. Be sure and reserve your hotel early in the future.

As of January 2, Bill Steiger has become the new program director for theoretical computer science at the NSF. He expects to fund 15-20+ awards from an estimated 100 theoretical computer science submissions to the Theoretical Foundations solicitation due this Thursday.

Richard Karp gave a long talk about the activities of the SIGACT Funding Committee. More on this in a future post.

Tom Leighton won the SIGACT Distinguished Service Award. The best student paper award winner was split between Anup Rao for Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources and Jakob Nordström for Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. The best paper award went to Irit Dinur for The PCP Theorem by Gap Amplification.

FOCS 2006 October 22-24 in Berkeley. STOC 2007 June 11-13 in San Diego as part of FCRC. STOC 2008 in Victoria, British Columbia May 18-20.

Favorite Theorems: Primality Algorithms

April Edition

For many years the standard example of a probabilistic algorithm checked whether a number was prime.

Riemann's Hypothesis and Tests for Primality, Gary Miller, STOC 1975, JCSS 1976.

A Fast Monte-Carlo Test for Primality, Robert Solovay and Volker Strassen, SICOMP 1977.

Probabilistic Algorithm for Testing Primality, Michael Rabin, Journal of Number Theory, 1980.

Let n be an odd number and n≠r^q for r,q>1. Fermat's little theorem shows that for any a, 1<a<n, if aⁿ≠a (mod n) then n is composite. But for a special set of composites called the Carmichael Numbers, this test will fail for all a. Miller adds the condition that a^(n-1)/2k-1 and n are relatively prime for all 2^k dividing n-1 and shows that assuming the Extended Riemann Hypothesis, for any composite n there is an a < O(log² n) passing the test. This gives a polynomial-time (in the number of bits to express n) algorithm for primality assuming ERH. Rabin showed that one could instead choose random a's giving a probabilistic algorithm with no assumption. The resulting test is now called the Miller-Rabin primality test. Solovay and Strassen give a different test based on the Jacobi Symbol.

Of course now we know that primality has a polynomial-time algorithm with no unproven assumptions. So why did I choose these obsolete algorithms for favorite theorems? They are not so obsolete as they are considerably more efficient then Agrawal-Kayal-Saxena. But more importantly they served as the motivation for the study of probabilistic computation, much like Shor's Quantum Factoring Algorithm motivates quantum computing today. Without studying probabilistic computation we would have had no modern cryptography, no derandomization results, no Toda's theorem, no interactive proofs and no probabilistically checkable proofs with their hardness of approximation consequences.

Taulbee Survey

Via CRA Bulletin the 2004-2005 Taulbee Survey has been posted. A wealth of statistics about computer science in the US and Canada. The charts fall into several major categories.

1. Ph.D. Production and Employment. Most CS Ph.D's ever (1189) last year. Nearly all of them found jobs.
2. Bachelor and Master's Students. Enrollment continues to decline.
3. Faculty Demographics. Faculty sizes continue to grow, though slowly, and are getting slightly more diverse.
4. Research and Graduate Student Support. A drop in research expenditures likely due to fewer grants.
5. Faculty Salaries. Truly useful when negotiating your pay. An interesting inversion where the schools ranked 13-24 in CS pay higher salaries than the schools ranked 1-12. And just who is being paid $400K?

The end of the report sums up the statistics nicely.

As predicted last year, our field is producing Ph.D.s at a record rate, and the short-term forecast is for continued record production. While there is no evidence in our employment statistics that the increased production is resulting in an inability of Ph.D. graduates to find work, an increasing fraction of new Ph.D.s appear to be taking positions outside of North America. In the wake of accelerating globalization of the marketplace, this is not surprising.

Three consecutive years of decreasing numbers of new Ph.D. students, and a sharply reduced pipeline at the Bachelor's level, will make it difficult to sustain this production rate in the longer term. Moreover, it is not yet clear when the decline in our undergraduate program enrollments will end. The double-digit percent decrease in bachelor's production observed this year is likely to continue for the next several years. Coupled with the declining representation of women in our undergraduate programs, our ability to produce a workforce that is sufficiently educated technically to meet the needs of the job market in computing is being severely challenged. The declining enrollments at the Bachelor's level also will increasingly challenge the ability of CS/CE departments to grow their faculty as they desire.

Graph Theory and the NSA

How could I not blog about Jonathan Farley's op-ed piece The NSA's Math Problem? Farley looks at the NSA's use of phone data as and argues that using graph theory to analyze the calls won't help find terrorists. But Farley doesn't do a particularly good job making his case.

First, the "central player" the person with the most spokes might not be as important as the hub metaphor suggests. For example, Jafar Adibi, an information scientist at the University of Southern California, analyzed e-mail traffic among Enron employees before the company collapsed. He found that if you naively analyzed the resulting graph, you could conclude that one of the "central" players was Ken Lay's…secretary.

Somehow if we find the "secretary" of a central US terrorist that should be considered a major success. But more importantly if we know just a little about some terrorist activities the graph can give us a great advantage in finding important sites. Google's PageRank primarily uses graph theory very successfully to rank order search results and there is no reason similar ideas won't work on phone data as well.

By no means should we accuse someone of being a terrorist solely because of their calling pattern. Will all terrorists be found on phone data alone? Of course not. But using graph information can give us important information as to where to look and narrow the search.

The main objection to the NSA's work is not that the phone data has little value but that it is too valuable. You can use the data to find out much more about Americans than who is a terrorist. We lose our freedom against government intrusion when the NSA has this data and that's what we need to argue against, not some fake argument that the NSA's algorithms won't work.

Steven Levy has a more reasonable discussion in Newsweek.

Computer Reliability

Suppose we could create a system where all automobile traffic in the US would be controlled by a central computer system. Traffic would flow more smoothly, fuel consumption could be better controlled, but with a catch that failures in the system could cause 10,000 deaths/year.

Keep in mind that we now have over 38,000 automobile fatalities per year. Even if we leave out alcohol-related deaths that number drops only to about 24,000. Still the public would find 10,000 deaths unacceptable and we would junk a system that would actually save lives as well as time and fuel.

I find when we frame the debate on the unreliability of computers, we usually measure it against perfection, rather than measuring it against the status quo. Whenever I read the Inside Risks column at the end of each CACM, I feel they fail to point out how little the risks are compared to the advantages of computing, instead of pointing out how bad the risks compared to unachievable perfection.

Consider electronic voting. I noticed that Diebold, the company in the middle of the electronic voting controversy, also makes the ATMs I use to withdraw money from my bank. ATMs are not foolproof, thieves have managed to fake ATM cards and discover passcodes to steal money from these machines. But banks know that the labor cost savings they get from ATMs greatly outweigh the losses.

Will electronic voting ever completely prevent any kind of fraud? Of course not. But will it beat out the systems we currently have in place? That's not that high a bar to pass.

I can vote proxies on my stocks and mutual funds over the Internet. There are some real money issues involved in the proxies. If Internet voting works well enough when serious money is involved, why can't we use it for general elections as well?

FCRC

This Monday May 15th is the early registration deadline for this year's Conference on Computational Complexity in Prague. The early registration date for the Electronic Commerce (EC) conference is Tuesday the 16th.

Next year both Complexity and EC will be part of the Federated Computing Research Conference (FCRC) in San Diego along with a plethora of other conferences including STOC, Computational Learning Theory (COLT), and Parallel Algorithms and Architecture (SPAA). June 13th is the day of death: STOC (2 tracks), EC, Complexity and COLT all have sessions that day. A theorist could find him or herself wanting to see five talks all given at the same time.

Game Science

Ehud Kalai proposes renaming the Game Theory Society to the Game Science Society and welcomes your comments. The goal of changing the name of the society is to change the name of the field to better describe what the field does and broaden its image.

An important example where the expanded name may get additional support is within a university. For example, it is hard to imagine the creation of a department devoted to the study of a theory. On the other hand a department devoted to study a science seems more plausible. To put things in perspective think of an analogy within another young field. Devoting major resources to a subject called "computing theory" less likely than devoting major resources to a subject called "computer science."

I've mentioned changing the name of Game Theory before but then again I never felt Computer Science is a great name. Following Kalai's reasoning, what if we renamed "Theory of Computing" to "The Science of Computing". Would that make our field sound more noble and generate more funding?

The Importance of Natural Proofs

Razborov and Rudich's paper Natural Proofs gives a combinatorial framework for proofs to show that circuits in a given class cannot achieve a given computational task. The paper explains the difficultly of extending these proofs to show, for example, that NP does not have polynomial-size circuits (and thus P≠NP). But do natural proofs really present a barrier to proving important circuit lower bounds?

One approach to showing NP does not have polynomial-size circuits: Find some property C of functions such that SAT is in C. We then show, using some sort of inductive argument, that no function computable by polynomial-size circuits can have property C. This would imply SAT, cannot have polynomial-size circuits.

Briefly a natural proof is such a proof where C has two properties.

1. Largeness: C contains many functions.
2. Constructivity: One can efficiently verify that a function f is in C.

Razborov and Rudich show that such a proof against polynomial-size circuits would break pseudorandom generators and in particular imply that the discrete logarithm is not hard. So under reasonable hardness assumptions, natural proofs cannot be used to prove lower bounds against polynomial-size circuits. See the paper for more details.

Sounds bad for proofs against circuits. But let's consider the two properties. The authors give a good argument why the largeness condition should hold, however

We do not have any similar formal evidence for constructivity, but from experience it is plausible to say that we do not yet understand the mathematics of C_n outside exponential time (as a function of n) well enough to use them effectively in a combinatorial style proof. We make this point in Section 3, where we argue that all known lower bound proofs against nonmonotone circuits are natural by our definition.

Indeed they do show all known proofs are natural, but in some cases go through considerable effort to "naturalize" these proofs (as opposed to relativization where the fact that a theorem relativizes follows immediately from the proof).

Consider what I call quasinatural proofs, where we only require the largeness condition. One might say that if discrete logarithm is hard then a quasinatural proof must prove the nonconstructivity of C. But really you get a conditional. If there are quasinatural proofs against polynomial-size circuits then

If C is constructive then Discrete logarithm is easy which is just a "pigs can fly" theorem that we see often in complexity.

Avi Wigderson points out that unconditionally you cannot have a natural proof showing that the discrete logarithm problem is hard. If we unravel this statement then we get that giving a quasinatural proof showing discrete logarithm is hard would require proving that discrete logarithm is hard, hardly a surprise.

I don't have an example of a quasinatural proof not known to be natural as we have very limited techniques for proving circuit lower bounds. Natural proofs do give us some insight into what kind of proof techniques we need for stronger lower bounds, but they do not, in and of themselves, present a major barrier to finding such proofs.

Forward-Looking Links

A computer science paper goes through many phases: manuscript, technical report, conference submission and proceedings and journal submission and published version. As a paper goes through these stages they usually improve, adding more background and intuition, better and more detailed proofs and so on. If someone wants to read your paper, you'd like them to look at the latest version. How do you make sure that they even know about the latest version?

You can't go into everyone's paper proceedings and add a yellow sticky to your paper saying to check out the new and improved journal version. But in this electronic age we can, in principle, add these notes.

First of all keep the papers on your webpage up to date. Many people just go to an author's page to download a paper and often they find some ancient version.

But after that then what? ECCC allows one to submit a revised version or add a comment which could point to a revised version. arXiv allows one to add journal information to an existing paper. Both of these require actions by authors that rarely happen. The digital libraries of proceedings publishers ACM and IEEE-CS don't have any mechanism to add pointers to later papers.

The field should have some standard mechanism for updating pointers to future papers. Until then we have to rely on the readers to find the latest papers on their own and perhaps hope that paper search tools like Citeseer, Google Scholar and Microsoft Academic Search will point to the latest and greatest version of a paper.

Rejection and Rejecting

Luca and Oded talk about rejection. Here are some thoughts.

Rejection hurts. Academics thrive on earning the respect of their peers and it's tough to think that someone doesn't want you. So go ahead and be depressed for a day or two and then move on.

Stanford is my ultimate rejecter, having turned me down for undergrad, grad, junior and senior faculty positions without the least bit of interest. But I got my revenge–I once got a parking ticket at Stanford and I never paid it. Ha!

A few people have complained to me about how rejections letters are written. A rejection letter contains exactly one bit of useful information. The rest is irrelevant and you should not let it get to you.

Suppose Alice sends email to her friend Bob asking if Bob's department would be interested in her. In academics, Bob usually won't give his real thoughts ("We are looking for strong candidates and you are not one of them"), instead he'll find some property P such that Alice has P but they won't hire in P, for example "Unfortunately we are not looking for any cryptographers this year." A couple of warnings for Bob:

1. Be sure P is not illegal, i.e., based on religion, race, gender, etc. Even if you don't discriminate, saying that you do is not a smart thing.
2. Bob's department might end up hiring a cryptographer. Then Alice will realize that Bob didn't want Alice because she was a cryptographer, rather he just didn't want Alice.

The Cost of Big Science

A panel at the National Academy of Sciences suggests that the US should support Fermilab's bid to land the International Linear Collider.

via Chicago Sun-Times

As a scientist I should support such a project, especially one located in the suburbs of Chicago. But at what cost? As a perspective, next year's proposed budget for the entire National Science Foundation is just over $6 billion.

This ILC reminds me of the Superconducting Super Collider, a project that spent $2 billion dollars digging a hole in Texas that was killed by Congress in 1993 once the projected costs topped $12 billion.

Putting large dollars into a single basket will take away the incentive to increase basic research funding in other scientific endeavors. The main argument for the ILC at Fermilab is not that the research won't get done, it just won't get done in the US. So let the Europeans or the Japanese have the flashy expensive collider and let the US do what it does best—basic research advancing science over a large range of disciplines.

Four Coloring the United States

For a talk I wanted to show a map of the United States using four colors with the usual constraint that every pair of states that share a common border have different colors. The four-color theorem says that such a coloring must exist.
So I tried Googling to find such a picture of a four-colored United States but I couldn't find one. NASA states it as a challenge but doesn't give the solution. Most maps I found like this one

use five or more colors, probably because they use a simple greedy algorithm.

Four coloring the US is not difficult. I found a Map Maker utility that lets you color the states anyway you want. Here is my four coloring.

My independent sets:

1. AK, AL, AR, CT, DE, HI, IL, ME, MI, MN, MT, NE, NM, NV, SC, VA, WA
2. AZ, DC, FL, KS, KY, MS, NC, ND, OR, PA, RI, TX, VT, WI, WY
3. CA, CO, GA, ID, IN, LA, MA, MO, NJ, SD, WV
4. IA, MD, NH, NY, OH, OK, TN, UT

The United States cannot be three colored, just consider Nevada and its neighbors. When writing this post I Googled on "four-color theorem" and the first link was this page which features a four-colored United States. Well at least I got a weblog post from all this work.