Columbia University Department of Computer Science



New York Area Theory Day

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

Friday, December 7, 2007

New York University, Courant Institute of Mathematical Sciences
Room 109 Warren Weaver Hall 
251 Mercer Street 
New York, NY 10012

The New York Area Theory Day is a semi-annual conference, aimed to bring together people in the New York Metropolitan area for one day of interaction and discussion.  The Theory Day features several (usually 4-5) hour-long presentations by leading theoretical computer scientists about state-of-the-art advances in various areas.  Some presentations give a survey of the latest advances in some area, while others may concentrate on a particular result.  
The meeting is free and open to everyone; in particular, students are encouraged to attend.


 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  
The Theory Day will be held at Room 109 Warren Weaver Hall,
Courant Institute of Mathematical Sciences, New York University, 
251 Mercer Street, New York, NY 10012
Click here or here (building 46) for directions. 
To subscribe to our mailing list, follow instructions here.


Yevgeniy Dodis (NYU)

Tal Malkin (Columbia University)

Tal Rabin (IBM Research)

Baruch Schieber (IBM Research)


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.
  "Every day is Theory Day"