Quick post on first day of STOC 2009

Shafi Goldwasser just won the 2009 ACM Athena Award at STOC. What a great choice, she is one of the leaders in theory and in particular cryptography. Congratulations Shafi. She was introduced, for her talk, by Cynthia Dwork, who gave one best introductions I have ever heard. It was well thought out and well delivered.

Shafi’s lecture was on cryptography, of course. She raised a number of problems in the basic models that are used in most crypto-results. In particular, Shafi talked about side-channel attacks. Since modern crypto-systems seem to be hard to break head-on, they are sometimes defeatable by breaking the model. This always reminds me of one of my favorite Far-Side cartoons: The indians are attacking the cowboys, who are in a wooden fort–the kind used in the wild west in the 1880’s. The arrows of the indians are flaming arrows, which are starting the fort to burn. One of the cowboy asks another one, “are they allowed to do that?”

Side channel attacks fall into two main types: memory attacks and computation attacks. The first are attacks that use physical means to recover parts of the secret keys; the second are attacks that leak bits as the protocols are executed. Shafi outlined the known results, and presented some new results that show that it may be possible to defend against many types of side channel attacks. I am sure that there will be many more results on this in the future.

Some Highlights

I have been to a number of talks, and would like to share some initial thoughts on the conference. I also have been Twittering about the talks too–so you can follow me there.

The conference is two-way parallel, except for the “big” talks like Shafi’s. Albert Meyer once told me that the advantage of a two-way parallel conference was that when he stayed in the hall to talk to friends, he only missed ${1/2}$ of the conference. I pointed out that, from this point of view, the optimal conference would have all ${n}$ of the papers at once. That way if you stayed in the hall, you would only miss ${1/n}$ of the conference. Albert thought that this was a great idea. One of my early unpublished results.

${\bullet}$ Linda Sellie gave a great talk on a beautiful result on exact learning of DNF. She showed that if a DNF formula was selected from a reasonable random distribution, she could almost always exactly learn it in polynomial time from uniform samples.

${\bullet}$ László Babai gave a terrific talk on the latest results on matrix groups. The short answer is that for such groups over finite fields of odd characteristic he can give tight bounds on the computational cost of the basic questions about such groups. An exciting point he made in his talk is that that group theorists are now getting involved in complexity related results. This is joint work with Robert Beals and Ákos Seress.

${\bullet}$ Swastik Kopparty gave a wonderful talk on dispersers. He made the problem clear, gave us an idea of the solution, and in general gave a very good talk. The results seem extremely interesting and have connections to many other problems in theory, in my opinion. This is joint work with Eli Ben-Sasson.

${\bullet}$ Constantinos Daskalakis gave a clear talk on what he calls “oblivious” strategies for games. The key insight is that many results in this area are oblivious to the structure of the game, and only need to know the strategies. With this restriction he could prove some new upper and lower bounds. A very nice set of results. This is joint work with Christos Papadimitriou.

${\bullet}$ Valentine Kabanets gave a masterful presentation of new results on testing of direct product codes. The great aspect of this work is that there are applications to PCP and other problems. The proofs, while non-trivial, are clearly simpler than previous proofs.

At one point he had a diagram on the screen that looked like the famous “flower” lemma from combinatorics. I was sitting next to Alexander Razborov, and I said “that looks familiar”–the flower lemma is key in one of his famous lower bound results. He was puzzled and only after the talk did he get my point. This is joint work with Russell Impagliazzo and Avi Wigderson.

${\bullet}$ Eric Blais gave a property testing talk on Juntas. At the beginning he said that the Junta was size ${k}$ and ${n}$ was the total number of variables. I asked, could ${k}$ be larger than ${n}$? He looked at me like I was out of it. It was a joke: you know, five academics can have ten opinions on anything. Cynthia Dwork told me later, she liked the joke. Oh well. There is a comedy club at the Hyatt, I think I’ll not be trying out there anytime soon.

Open Problems

I guess the main open problem for me is to get to more talks, and stop writing this post. I plan a normal post that should be out soon.