New York Area Theory Day

New York University, Courant Institute of Mathematical Sciences
Room 109 Warren Weaver Hall 
251 Mercer Street 
New York, NY 10012
 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. 

  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" 

New York Area Theory Day

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

Program:

Organizers:

Abstracts:

New York Area Theory Day

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

Program:

Organizers:

Abstracts:

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