## 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.
### 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
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.
### Organizers:
Yevgeniy Dodis (NYU)
Tal Malkin (Columbia University)
Tal Rabin (IBM Research)
Baruch Schieber
(IBM Research)
### 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.
"Every day is Theory Day" |