New York Area Theory Day

Organized by: IBM/NYU/Columbia
External sponsorship by: Google

Friday, December 7, 2007
The Theory Day will be held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

Program

9:30 - 10:00 Coffee and bagels

10:00 - 10:55 Prof. Luca Trevisan
Dense Subsets of Pseudorandom Sets

10:55 - 11:05 Short Break

11:05 - 12:00 Dr. Benny Applebaum
Cryptography in Constant Parallel Time

12:00 - 2:00 Lunch break

2:00 - 2:55 Dr. Emanuele Viola
Polynomials: New results via Gowers norm

2:55 - 3:15 Coffee break

3:15 - 4:10 Prof. Scott Aaronson
Quantum Copy-Protection

Organizers:

Yevgeniy Dodis dodis@cs.nyu.edu
Tal Rabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com
Rocco Serverdio rocco@cs.columbia.edu

Abstracts

Dense Subsets of Pseudorandom Sets

Prof. Luca Trevisan
Institute for Advanced Study and Berkeley

A theorem of Green, Tao and Ziegler can be stated (roughly) as follows: if R is a pseudorandom set, and D is a dense subset of R, then there is a "model" set M for D such that M is a dense set and D and M are indistinguishable. (The precise statement refers to "measures" or distributions rather than sets.) The proof is very general, and it applies to notions of pseudorandomness and indistinguishability defined in terms of any family of adversaries. The proof proceeds via iterative partitioning and an energy increment argument, in the spirit of the proof of the weak Szemeredi regularity lemma. The "reduction" involved in the proof has exponential complexity in the distinguishing probability.

We present a new proof inspired by Nisan's proof of the Impagliazzo hard core set theorem. The reduction in our proof has polynomial complexity in the distinguishing probability and provides a new characterization of the notion of "pseudoentropy" of a distribution.

Following the connection between this theorem and the Impagliazzo hard core set theorem in the opposite direction, we present a new proof of the Impagliazzo hard core set theorem via iterative partitioning and energy increment. While our reduction has exponential complexity in some parameters, it has certain consequences that do not seem to follow from known proofs.

This is joint work with Omer Reingold, Madhur Tulsiani and Salil Vadhan.

Cryptography in Constant Parallel Time

Dr. Benny Applebaum
Princeton University

We will survey a number of recent results on the parallel time-complexity of basic cryptographic primitives such as one-way functions, pseudorandom generators, encryption schemes and signatures. Specifically, we will consider the possibility of computing instances of these primitives by NC0 functions, in which each output bit depends on only a constant number of input bits. While NC0 functions might seem too simple to have cryptographic strength, we will show that, under standard cryptographic assumptions (e.g., that integer factorization is hard), most cryptographic tasks can be carried out by functions in which every bit of the output depends on only four bits of the input. We will also examine the possibility of carrying out cryptographic tasks by NC0 functions which have the additional property that each input bit affects only a constant number of output bits. We will characterize which cryptographic tasks can be performed by such functions.

This is joint work with Yuval Ishai and Eyal Kushilevitz. The talk is self-contained, and does not assume previous background in cryptography.

Polynomials: New results via Gowers norm

Dr. Emanuele Viola
Columbia University

Polynomials are fundamental objects in computer science that arise in a variety of contexts, such as error-correcting codes and circuit lower bounds. Despite intense research, many basic computational aspects of polynomials remain poorly understood. For example, although it is known that most functions cannot be approximated by low-degree multivariate polynomials, an explicit construction of such a function is still unknown.

Recently, we have studied computational aspects of polynomials via a new tool known as ``Gowers norm,'' which was introduced in combinatorics by Gowers ('98) and independently in computer science by Alon, Kaufman, Krivelevich, Litsyn, and Ron ('01). In this talk I will describe Gowers norm and present some of its applications to computer science. In particular, I will show how this norm lets us construct pseudorandom generators for low-degree polynomials, a result which marks the first progress on this problem since 1993.

Based on joint work with Avi Wigderson and on joint work with Andrej Bogdanov.

Quantum Copy-Protection

Prof. Scott Aaronson
MIT

In the classical world, giving people computer programs that they can use but not copy is fundamentally impossible -- not that that's stopped companies from spending millions of dollars trying! In the quantum world, though, the famous No-Cloning Theorem changes the nature of the question and makes it much more interesting. So in this talk I'll ask: can someone give you a quantum state that lets you efficiently compute a function f, but that doesn't let you efficiently prepare *more* quantum states from which f can be computed? My main result is that there exists a "quantum oracle," relative to which every function that isn't learnable from inputs and outputs can indeed be quantumly copy-protected in this sense. In other words, either copy-protection is "generically" possible in the quantum world. or else it will be hard to prove it isn't! I'll also propose an explicit candidate scheme for copy-protecting point functions (Boolean functions f such that f(x)=1 for exactly one x), which is secure under a new computational assumption related to (but stronger than) the hardness of the Nonabelian Hidden Subgroup Problem.