Computer Science Colloquium
The IBM Research NYU/Columbia Theory Day
Friday, May 22, 2009
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 SubConstant 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 and Rutgers University)
3 Problems in Internet Ad Systems
For directions, please see: http://www.cs.columbia.edu/theory/directions.html
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
TalRabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com
Rocco Serverdio rocco@cs.columbia.edu
Abstracts
Two Query PCP with SubConstant Error
Dr. Dana Moshkovitz
(IAS)
We show that the NPComplete language 3Sat has a PCP verifier that makes
two queries to a proof of almostlinear size and achieves subconstant
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 twoquery projection tests, but only (arbitrarily small) constant
error and polynomial size. There were also PCP Theorems with
subconstant error and almostlinear 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
nearlyoptimal amortized query complexity and free bit complexity
(SamorodnitskyTrevisan, 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. Latticebased 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
publickey 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 serveraided 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 boundeddepth (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 boundeddepth Boolean circuits cannot
distinguish polylogarithmically 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)
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 $11/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 EvenDar, Mansour, Mirrokni and Nedev.
top  contact webmaster@cs.nyu.edu
