Cryptography at STOC/FOCS

It has been too long and now there is no point telling stories from the last two days of FOCS, such as the distinguished theoretician who “flew” on the zip-line on Fremont street and then got drunk at Double Down and asked the two big scary guys who were playing pool if they were twins (they said they were).

As soon as the videos of the conference go online, however, I would suggest to everybody who wasn’t there to watch Dan Spielman’s invited talk, which was phenomenal. Dan talked about the problem of solving linear equations when the constraint matrix is the Laplacian of a graph, the result of a long-term collaboration with Shang-hua Teng. Two major parts of this research program have gone on to become their own research area:

You Read it Here First

Last year, I wrote on the losing tactic of promoting oneself by disparaging the competitors, using a parable attributed to Silvio Micali.

This week a Dilbert cartoon covers the same ground.

So this is what “FOCS” stands for

At the STOC 2009 business meeting, Silvio Micali announced a new conference, Innovations in Computer Science (ICS), whose first edition will be in Beijing in January, 2010.

This is a conference that aims to be the venue for the first papers in new areas. This prompted people to ask me afterward if we shouldn’t start a new conference devoted to second papers. I thought this was an appealing ideas, and perhaps the conference could be called Follows-up in Computer Science; a snarky colleague, however, suggested that we already have two such conferences and they are called STOC and FOCS.

ICS has a steering committee entirely composed of past and future Turing Award winners, so surely they know what they are doing. A common complaint I heard, however, was that it isn’t clear exactly what the motivations and the goals of this conference are, what papers are being sought (surely you cannot fill up a 30-paper conference with first papers, each opening up a new area), and so on.

Helpfully, Oded Goldreich, one of the promoters of ICS, has written a statement about the goals ICS, as well as a longer essay on What is wrong with STOC and FOCS. The arguments made in the essay are Oded’s motivations for the new conference.

As I have said before, I agree with the importance of conceptual innovations, and of simplicity, but I disagree with the claim that our current review system undervalues such points. Hence, I think that initiatives such as the “letter on conceptual contributions” and now ICS will not correct an imbalance, but rather will create an imbalance, penalizing the necessary, hard, and unglamorous technical work by which we understand new ideas, exploit and simplify their applications, and create the conditions such that the next new ideas are “in the air” and the right person at the right time can get them, and so on.

Changes I’d like to see in STOC/FOCS

• Create a “test of time award” going to the paper from the STOC/FOCS ten years prior which has best stood the test of time;
• Reverse the trend of theoretical cryptography becoming the new computational geometry, splitting off into a self-contained community;
• Increase the size of the program committee so that no PC member has to review more than 30 papers;
• Allow PC members to submit papers;
• Videotape the talks and post them on the web;
• Hold either STOC or FOCS in Asia at least once;
• Hold STOC and FOCS in Canada more often;
• Always have beer at the business meeting and drinks at the reception. No exceptions;
• Make it a rule that the PC Chair and the local organizer can present at most one piece of statistical data each at the business meeting; their presentations cannot exceed five minutes in total.

On a more practical note:

• Let a substantial part of the discussion at the physical PC meeting be “caucus” groups in which clusters of papers in a related areas are discussed by the experts, and the controversial papers can be discussed at a technical level. There are about 15 hours of work in a two-day meeting, devoted to the discussion of 100+ papers plus several meta-questions, so most papers must be discussed in less than 10 minutes. With such time constraints, and with a group of 20+ people, the discussion of a controversial paper becomes a debate, in which the point is winning. In a smaller context, in which everybody understands the paper, it is easier to reach a consensus.