==========================================================================
The IBM Research|NYU|Columbia Theory Day
Friday, May 22, 2009
The Theory Day will be held at the Davis auditorium,
412 Schapiro (CEPSR) building, Columbia University, New York.
Program
9:30 - 10:00 Coffee and bagels
10:00 - 10:55 Dr. Dana Moshkovitz (IAS)
Two Query PCP with Sub-Constant Error
10:55 - 11:05 Short break
11:05 - 12:00 Dr. Craig Gentry (IBM Research)
Fully Homomorphic Encryption Using Ideal Lattices
12:00 - 2:00 Lunch break
2:00 - 2:55 Dr. Mark Braverman (Microsoft Research)
Approximating bounded depth circuits with polynomials
2:55 - 3:15 Coffee break
3:15 - 4:10 Dr. Muthu Muthukrishnan (Google Labs & Rutger University)
3 Problems in Internet Ad Systems
For directions, please see
http://www.cs.columbia.edu/theory/directions.html
To subscribe to our mailing list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/theory-ny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
Rocco Servedio rocco@cs.columbia.edu
Tal Rabin talr@us.ibm.com
Baruch Schieber sbar@us.ibm.com
==================================================================
Abstracts
Two Query PCP with Sub-Constant Error
Dr. Dana Moshkovitz
(IAS)
We show that the NP-Complete language 3Sat has a PCP verifier that makes
two queries to a proof of almost-linear size and achieves sub-constant
probability of error o(1). The verifier performs only projection tests,
meaning that the answer to the first query determines at most one
accepting answer to the second query.
Previously, by the parallel repetition theorem, there were PCP Theorems
with two-query projection tests, but only (arbitrarily small) constant
error and polynomial size. There were also PCP Theorems with
sub-constant error and almost-linear size, but a constant number of
queries that is larger than 2.
Our theorem improves many of the hardness of approximation results that
are proved using the parallel repetition theorem, such as those of 3SAT
and 3LIN (Hastad, 97), or the PCP Theorems with
nearly-optimal amortized query complexity and free bit complexity
(Samorodnitsky-Trevisan, 00).
Joint work with Ran Raz.
==================================================================
Fully Homomorphic Encryption Using Ideal Lattices
Dr. Craig Gentry
(IBM Research)
We propose a fully homomorphic encryption scheme, i.e., a scheme that
allows one to evaluate circuits over encrypted data without being able
to decrypt. Our solution comes in three steps. First, we provide a
general result that, to construct an encryption scheme that permits
evaluation of arbitrary circuits, it suffices to construct an encryption
scheme that can evaluate (slightly augmented versions of) its own
decryption circuit; we call a scheme that can evaluate its (augmented)
decryption circuit bootstrappable.
Next, we describe a public key encryption scheme using ideal lattices
that is almost bootstrappable. Lattice-based cryptosystems typically
have decryption algorithms with low circuit complexity, often dominated
by an inner product computation that is in NC1. Also, ideal lattices
provide both additive and multiplicative homomorphisms (modulo a
public-key ideal in a polynomial ring that is represented as a lattice),
as needed to evaluate general circuits.
Unfortunately, our initial scheme is not quite bootstrappable i.e.,
the depth that the scheme can correctly evaluate can be logarithmic in
the lattice dimension, just like the depth of the decryption circuit,
but the latter is greater than the former. In the final step, we show
how to modify the scheme to reduce the depth of the decryption circuit,
and thereby obtain a bootstrappable encryption scheme, without reducing
the depth that the scheme can evaluate. Abstractly, we accomplish this
by enabling the encrypter to start the decryption process, leaving less
work for the decrypter, much like the server leaves less work for the
decrypter in a server-aided cryptosystem.
We will also review some applications, such as encrypted Google queries,
searching on encrypted databases, and applications to general multiparty
computation.
==================================================================
Approximating bounded depth circuits with polynomials
Dr. Mark Braverman
(Microsoft Research)
I will talk about the problem of approximating bounded-depth (AC0)
Boolean circuits with polynomials over the reals. I will present some
classical results, and then a new approximation construction. The new
construction implies that bounded-depth Boolean circuits cannot
distinguish poly-logarithmically independent distributions from the
uniform one, settling a 1990 conjecture by Linial and Nisan.
==================================================================
3 Problems in Internet Ad Systems
Dr. Muthu Muthukrishnan
(Google Labs and Rutgers University)
We present 3 recent results in internet ad systems:
-- [Stochastic online matching] We are given a "stochastic bipartite
graph" (L, R, E) with a probability distribution over nodes in R.
Nodes in R arrive online -- drawn independently, randomly, from the
given distribution --- and need to be assigned to their neighbors
upon arrival. We need to maximize the size of the matching on the
online instance. We present a better than $1-1/e$ online,
approximation algorithm for this problem that is motivated by display
ads allocation. Joint work with Feldman, Mehta, and Mirrokni.
-- [Configuration Bidding] Currently ad platforms and publishers
determine the configuration of ads (for example, the number of ads
shown). What if the bidding language lets advertisers directly
determine the configurations? We propose a suitable auction for
configurations.
--[Broad Match Bidding] Advertisers use "broad match" feature to
target keyword variations in user queries. But this implicitly commits
their bids to auctions where their values may be quite different from
their bids. We study hardness and approximations for the problem of
determining how to bid for broad match in presence of budgets.
Joint work with Even-Dar, Mansour, Mirrokni and Nedev.
===========================================================================