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.

## 6 comments

Comments feed for this article

October 24, 2006 at 2:29 pm

David MolnarThanks for summarizing the new SZK result! It may be worth mentioning that there exists an oracle relative to which one-way functions exist, but one-way permutations do not. Rudich showed this was true assuming a combinatorial conjecture, and then Clifford, Saks, and Smythe proved the conjecture in 2000:

http://www.math.cmu.edu/~csmyth/Papers/conf.ps

I’ve always found this black-box separation beautiful and a bit surprising. While key agreement seems ‘obviously’ harder than constructing one-way functions, it isn’t obvious at first that the same should be true for one-way permutations. The separation also, in my mind, says something about why the new SZK result is a big deal.

October 25, 2006 at 11:12 pm

Eli ManevaLuca, it’s interesting the way you put this:

“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. “

It almost seems like the invited talks were just a sharade for the NSF. This angle was not taken by any of the accepted talks that I saw. Do you think this may be where the FOCS/STOC community has leaked a lot of people – those who would rather be funded, then get accepted to FOCS/STOC?

October 26, 2006 at 3:12 am

LucaEli, I definitely did not mean it that way. The way computational thinking is influencing other sciences is a fascinating one, and I learnt a lot through the invited talks, especially from Jon’s talk. The talks were just for us theoreticians.

I also believe the SIGACT committee has been talking to various people at NSF about the importance of this development, and then increased funding for theory may come from this. This is not a made-up story, it’s a very exciting development that should be adequately nurtured (and publicized).

October 26, 2006 at 1:05 pm

David MolnarLuca, has anyone mentioned whether ideas from theory are making an impact in philosophy, by the way? Proofs of knowledge, for example, give a computational account of what it means to “know something,” but I don’t know how widely they are known outside CS.

There’s also Scott’s work on the complexity of agreement. I remember Ben Blum was working on some algorithmic problems in philosophy at one point, as well. I unfortunately don’t remember the details. Probably there are more and better examples.

While connections with philosophy are probably not going to attract a lot of funding, it’s still fascinating to see how some of these ideas apply to age-old problems. Especially given the talk on sociology that you report in the other post.

October 26, 2006 at 4:07 pm

LucaThat’s also an interesting point, David. Philosophy, by the way, has a tradition of adopting mathematical tools, as appropriate. When I was a graduate student, I took a course on typed lambda calculus (don’t ask) following Girard’s book

Proofs and types, and the instructor was a professor in the Philosophy department whose research was in linear logic. In many Philosphy departments you will find logicians, recursion theorists, and category theorists that could as well be hosted in a Math department.October 30, 2006 at 2:38 am

Anonymouswhy did dick karp and christos papadimitriou wear a black shirt on that day?