Abstracts for the talks are given below. See the main page for schedule and location information.

(Joint work with Mihalis Yannakakis.)

We consider the online problem of non-preemptive queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. This corresponds to the well known and strongly motivated Naor's model in operations research.

We give a queue management algorithm with a competitive ratio equal to the golden ratio ($\phi\approx 1.618$) in the case that all packets have the same value, along with a matching lower bound. We also derive $\Theta(1)$ upper and lower bounds on the competitive ratio when packets have different intrinsic values in the case of differentiated services. We can extend our results to deal with more general models for loss of value over time.

Finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor.

Joint work with Amos Fiat and Yishay Mansour.

Computation is an ubiquitous phenomenon in nature, and of increasing relevance to many fields such as economics, biology, and mathematics. In this talk we survey some of our results in two surprisingly interrelated areas that are central to the understanding of computation: lower bounds and the power of randomness.

In particular, we consider the fundamental problem of following a path in a graph whose edges are distributed among several collaborating players. We obtain a lower bound on the amount of communication that the players need to exchange, answering a decade-old question. We also consider the problem of constructing sequences of bits that ``look random'' though being generated with little or no randomness. Here we present a pseudorandom generator that stretches few random bits into a long sequence which looks random to polynomials. Our result marks the first progress on this problem since 1993, and has spurred interaction between computer scientists and mathematicians, leading to advances on an outstanding conjecture in combinatorics.

Solving a polynomial system of equations is NP-hard, and therefore very hard in practice. However, this problem is at the root of many important applications, including algebraic cryptanalysis. Many techniques exist to tackle these problems, such as Groebner Bases methods, SAT-solvers, Linearization, and simple brute-force guess-and-check. The security of block and stream ciphers depends directly on the difficulty of solving systems of this type.

All of those methods are heavily dependent on the number of variables. The technique which will be presented today partitions the system into two distinct parts, which are otherwise connected only by a small number of variables which need to be guessed. So for example, consider a system of 100 variables and equations, with a small "bridge set" of 20 variables that connects two parts of the system. We show how to identify the presence and membership of the bridge, and thus break the system in two. The 20 variables must be guessed, but solving two 40 variable systems 220 times is much closer to feasible (261 work if using brute-force) than solving the original (2100 work if using brute-force). Potentially, this could move infeasible problems into the realm of feasibility.

A non-malleable encryption scheme is one wherein given an encryption of a message, it is infeasible to generate an encryption of a related message. We show how to transform any semantically secure encryption scheme into a non-malleable one, with a black-box construction that achieves a quasi-linear blow-up in the size of the ciphertext. This improves upon the previous non-black-box construction of Pass, Shelat and Vaikuntanathan (Crypto '06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt '07).

Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions in zero-knowledge. Instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. We exploit the fact that low-degree polynomials are simultaneously good error-correcting codes and a secret-sharing scheme.

Joint work with Seung Geol Choi, Tal Malkin, and Hoeteck Wee.

In this talk, I will describe a new extremely simple proof of the +1 result. Then I will discuss extensions to directed graphs, matroids and more general network design problems. Most of the talk will consist of giving a flavor of the polyhedral techniques used in the design and analysis of these algorithms.

Joint work with Rohit Khandekar and Viswanath Nagarajan.

Joint work with Boaz Barak

We show how to realize lossy TDFs under various number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of standard lattice problems. Taken all together, our results resolve some long-standing open problems in cryptography: they give the first known (injective) trapdoor functions based on problems not directly related to integer factorization, and provide the first known CCA-secure cryptosystem based solely on worst-case lattice assumptions.

This is joint work with Brent Waters.

This is joint work with Florin Ciocan, Andre Chailloux and Salil Vadhan

In this talk we will survey some new developments in holographic algorithms.

-- An adversary may be unable to learn your bid in an online auction if the bid is encrypted; however, it could potentially modify the ciphertext to obtain one corresponding to a bid that is a dollar higher than yours.

-- An adversary that adaptively determines which electronic voting machines to break into during the course of an election has a better chance at influencing the outcome of an election than one that makes its choices before the election commences.

I will present new constructions of encryption schemes addressing each of these attacks. The first scheme guarantees that given an encryption of a message, it is infeasible to generate an encryption of a related message. The second improves upon an important building block used in constructing protocols for general multi-party computation that are secure against an adversary that adaptively corrupts up to one third of the parties. Compared to most previous constructions, our schemes are simpler, more efficient, and can be realized under a larger class of cryptographic assumptions.

(joint work with Seung Geol Choi, Dana Dachman-Soled and Tal Malkin.)

This is Joint Work with Sanjeev Arora, Subash Khot, David Steurer, Madhur Tulsiani and Nisheeth Vishnoi.

Valiant showed that classes of functions evolvable in his model are also learnable in the statistical query (SQ) model of Kearns widely regarded as almost as powerful as PAC learning. He also asked whether the converse is true.

We show that evolvability is equivalent to learnability by a restricted form of statistical queries. Based on this equivalence we prove that for any fixed distribution D over the instance space, every class of functions learnable by SQs over D is evolvable over D. Previously, only the evolvability of monotone conjunctions of Boolean variables over the uniform distribution was known. On the other hand, we prove that the answer to Valiant's question is negative when distribution-independent evolvability is considered. To demonstrate this, we develop a technique for proving lower bounds on evolvability and use it to show that decision lists and linear threshold functions are not evolvable in a distribution-independent way.

In this work we show that standard techniques for proving hardness amplification against a class of circuits require that same class of circuits to compute the Majority function.

Our work is most significant when coupled with the celebrated ``natural proofs'' result by Razborov and Rudich (J. CSS '97) and Naor and Reingold (J. ACM '04), which shows that most lower-bounding techniques cannot be applied to circuits that can compute Majority. The combination of our results with theirs shows that **standard techniques for hardness amplification can only be applied to those circuit classes for which standard techniques cannot prove circuit lower bounds.** This in particular explains the lack of strong average-case lower bounds for a number of circuit classes for which we have lower bounds.

Our results also show a qualitative difference between the direct product lemma and Yao's XOR lemma, and they give tight bounds on the number of queries needed for hardness amplification.

Joint work with Ronen Shaltiel.

Making this connection precise, we show the following result : If UGC is true, then for every constraint satisfaction problem(CSP) the best approximation ratio is given by certain simple SDP. Specifically, we show a generic conversion from SDP integrality gap instances to UGC hardness results. This result holds both for maximization and minimization problems over arbitrary finite domains. Using this connection between integrality gaps and hardness results we obtain a generic polynomial-time algorithm for all CSPs. Assuming the Unique Games Conjecture, this algorithm achieves the optimal approximation ratio for every CSP.

Unconditionally, for all 2-CSPs the algorithm achieves an approximation ratio equal to the integrality gap of the natural SDP. Thus the algorithm achieves at least as good an approximation ratio as the best known algorithms for several problems like MaxCut, Max2SAT and Unique Games.

Joint work with Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, and Hoeteck Wee.