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 CopyProtection
For directions, please see: http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/csweb/Location/directions.html (building 46)
To subscribe to our mailing list, follow instructions at: http://www.cs.nyu.edu/mailman/listinfo/theoryny
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 timecomplexity of
basic cryptographic primitives such as oneway 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
selfcontained, 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 errorcorrecting 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 lowdegree
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 lowdegree 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 CopyProtection
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 NoCloning 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 copyprotected in this sense. In other words, either
copyprotection 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 copyprotecting 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.
top  contact webmaster@cs.nyu.edu
