Off to a good start

FOCS 2006 is off to a good start with Salil's talk on Sunday morning on realizing statistical Zero-Knowledge arguments for all of NP assuming one-way functions. A zero knowledge proof systems has two important requirements: the proof system must be sound, that is, a cheating prover cannot convince a verifier that a wrong statement is true, and it must be zero knowledge, meaning that a cheating verifier cannot obtain any information by interacting with the prover. Each requirement can come in a statistical version (in which the cheating party can be arbitrarily powerful) or a computational version (in which the requirement holds only for computationally bounded cheating parties).

If both are statistical, we have a Statistical Zero Knowledge proof system, which cannot be achieved for NP-complete problems unless NP is contained in coAM. (Which is about as unlikely as having NP=coNP.) If soundness is statistical but zero knowledge is computational, we have Computational Zero Knowledge proof systems, which exist for all of NP assuming one-way functions.

What if we want computational soundness and statistical zero knowledge? It had been known that one could get such systems for all of NP assuming one-way permutations. Now, with this work of Nguyen, Ong and Vadhan, we finally know that one-way functions suffice for this version as well.

Before lunch, Richard Karp talks about the theme of theoretical computer science as a lens for the sciences. This has been an angle pursued for increased theory funding at NSF, and it is a theme that will recur in all the invited talks. Karp focuses on the case of computational biology. Christos Papadimitriou chairs the session. He says that when he interviewed at MIT, Dertouzos asked him who was his role model, and Christos answered "Dick Karp," an answer that Dertouzos seemed to like. When Karp starts speaking, he says "over time things have switched; now Christos is my role model, and this is why I am wearing black today."

The most enjoyable talk of the day is given by Swastik Kopparty, on joint work with Eli Ben-Sasson and Jaykumar Radhakrishnan. They consider the question of the optimality of the Sudan and Guruswami-Sudan list-decoding algorithms for Reed-Solomon codes. Optimality, that is, in terms of how many errors (or, equivalently, how low agreement) the algorithm can tolerate. The combinatorial question is at which point the size of the list that the algorithm has to compute becomes super-polynomial, precluding any possibility of a polynomial-time algorithm. They vastly improve previous such bounds. In the 20 minutes alloted for the talk, Swastik manages, with contagious enthusiasm, to explain the problem, to fully prove a weaker version of the result, which already slightly improves previous bounds, and to give a good idea of how the general argument looks like.

Xi Chen gives the talk for his paper with Xiaotie Deng on Nash equilibria that won the best paper award. They show that, even for two players, the problem of computing a Nash equilibrium is PPAD-complete, where PPAD includes all search problems in NP where the existence of a solution is guaranteed by a certain "fixed-point argument." In the longer time alloted for the paper award winner, Xi Chen explains the intuition that makes the two-player case seem easier than the case of three or more players, he describes previous results on the complexity of the cases of three or more players, and gives some idea of the new reduction. The talk is really excellent.

After dinner, the business meeting moves along unusually rapidly.

Sanjeev Arora thankfully does without the silly statistics on how many papers were accepted by number of authors and by length of the title, and simply offers the numbers of submissions, acceptance, and attendance. There are only about 220 registered attendants. (Plus a few unregistered ones as well, ehm, ehm.) This is about half the attendance at SODA. Isn't there something wrong going on, suggests Sanjeev? If (now it's me speaking, not Sanjeev) STOC and FOCS have, as a purpose, to be the place where the theory community comes together and we learn abotu results outside our area, but then the community does not come, haven't we lost our purpose?

FOCS 2007 will be in Providence, in a hotel that is currently under renovation, and Alistair Sinclair will be the program committee chair. The bid to hold FOCS 2008 in Philadelphia wins by acclamation against no opponent, despite bidder Sanjeev Khanna pleading not to accept his bid.

Umesh suggests that we move to an online publication of the proceedings and forgo the paper version. After some discussion, we vote for a dizzying array of possibilities. "Would you like to stop publishing proceedings, distribute a CD at the conference, but not do the online publication suggested by Umesh, while continuing the online publication in the IEEE digital library" was one of the options put to vote.