Colloquium Details
IBM Research NYU/Columbia Theory Day
Speaker:
Location: Schapiro (CEPSR) Building, Columbia University 412
Date: May 22, 2009, 9:30 a.m.
Host: Yevgeniy Dodis
Synopsis:
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 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 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)
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.
Speaker Bio:
Notes:
In-person attendance only available to those with active NYU ID cards.