STOC 2009

The list of STOC 2009 accepted papers is out and, in a very welcome innovation, abstracts are included.

I am looking forward to a number of talks. Among many others:

  • Craig Gentry will present a construction of homomorphic encryption based on the hardness of a lattice problem. In a homomorphic encryption scheme, given the encryption of {x} one can compute the encryption of {f(x)} for a class of functions {f()}, without knowing the decryption key and without gaining any partial information about {x}. According to the abstract, Gentry’s scheme works for all functions {f} in {NC1}. The existence of homomorphic encryption is one of the great open questions in cryptography. My guess had been that it is impossible for any reasonable large class of functions.

  • Ryan O’Donnell and Yi Wu have found a conditional solution (based on Khot’s “{d}-to-1 conjecture) to the problem of what is the best PCP with three queries and perfect completeness. This had been, for more than ten years, the only remaining open question on the power of three-query PCP.

  • Klim Efremenko has a sub-exponential 3-query locally decodable code construction that, unlike Sergey Yekhanin’s, does not rely on the existence of arbitrarily large Mersenne primes.

Also, Reid Andersen and Yuval Peres have devised a new approach to local graph partitioning, and I have been told that their ideas are genuinely new and likely to be applicable to other problems. I have been meaning to understand (and maybe post about) local graph partitioning algorithms, but probably this will not happen until the end of the cryptography class. Impagliazzo, Kabanets and Wigderson continue to explore “direct product” results, a staple of complexity theory which seemed settled in the early 1980s but that periodically generates new ideas and applications. In the new paper, some ideas from the beautiful STOC 2008 paper by Impagliazzo, Jaiswal, Kabanets and Wigderson are finding their way into PCP constructions. (A series of posts on direct products and “xor lemmas” is another of my post-CS276 plans.)