^January February – 2009 ^March

Jonathan Katz and Luca Trevisan defined the concept of Locally Decodable Codes (LDC). LDC are error correcting codes where a bit of the message can be probabilistically recovered by looking at a limited number of symbols of a corrupted encoding. After defining LDCs formally we will see some negative results. First, that local decoding is impossible when looking at only one symbol of the corrupted encoding. Then we will see a lower bound on the codewords' length.

This paper appeared in STOC00.

We are used to studing the runtime of algorithms as an increasing function of the data set size, and are happy when this increase is not so bad (e.g. when the runtime increases linearly, or even polynomiall, with the data set size). Traditional runtime analyzis of learning is also viewed this way, and studies how training runtime increases as more data is available. However, considering the true objective of training, which is to obtain a good predictor, I will argue that training runtime should actually be studied as a *decreasing* function of training set size. Focusing on training Support Vector Machines (SVMs), I will then present both theoretical and empirical results demonstrating how a simple stochastic subgradient descent approach indeed displays such monotonic decreasing behavior. I will also discuss a similar phenomena in the context of Gaussian mixture clustering, where it appears that excess data turns the problem from computationally intractable to computationally tractable.

Joint work with Shai Shalev-Shwartz, Karthik Sridharan, Yoram Singer, Greg Shakhnarovich and Sam Roweis

Verifiable random functions, introduced by Micali, Rabin and Vadhan, are a primitive aimed at coping with the absence of random oracles in the real world. While replacing the random oracle with a pseudorandom function can be a solution in some cases, its drawback is the function's seed owner's ability to adaptively change its answers and thus manipulate the protocol. In a verifiable random function, the seed owner produces a public-key at the beginning of the interaction, which constitutes a commitment to all (pseudorandom) values of the function. It can then produce, for any input, a proof that the output has been computed correctly (with respect to that public-key). Even a maliciously chosen public-key must not enable proving different outputs for the same input.

Verifiable random functions found various implementations and uses. However, no implementation based on a general assumption (such as the existence of one-way functions or even stronger assumptions like trapdoor permutations) is known.

We define a relaxation of verifiable random functions, which we call weak verifiable random functions, in the spirit of Naor and Reingold's weak pseudorandom functions. We show that this relaxed notion can be derived from various assumptions (including general assumptions); that the existence of weak verifiable random functions is essentially equivalent to the existence of non-interactive zero-knowledge proof systems for all of NP (in the common random string model); and prove that weak verifiable random functions (and thus also "standard" verifiable random functions) cannot be constructed from one-way permutations in a black-box manner, providing a first separation result for (standard) verifiable random functions from any cryptographic primitive.

No prior knowledge on black-box separations is assumed.

Joint work with Shafi Goldwasser, Guy Rothblum and Vinod Vaikuntanathan.

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (“buying price”), and cost proportional to the duration of the usage (“rental rate”). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems, where online choices cannot be modeled by just two alternatives, e.g., power management in systems which can be shut down in parts. In this work we study randomized online strategies for Multislope Ski Rental. Our results include an algorithm that produces the best possible randomized online strategy for any additive instance, where the cost of switching from one alternative to another is the difference in their buying prices; and an e-competitive randomized strategy for any (non-additive) instance. We also provide a randomized strategy with a matching lower bound for the case of two slopes, where both slopes have positive rents.

Joint work with Zvi Lotker and Boaz Patt-Shamir.

The Black-and-White Coloring (BWC) problem is defined as follows. Given an undirected graph $G$ and positive integers $b, w$, determine whether there exists a partial vertex-coloring of $G$ such that $b$ vertices are colored black and $w$ vertices white (with all other vertices left uncolored), such that no black vertex and white vertex are adjacent.

The BWC problem has been introduced in general, and proved to be $NP$-complete, by Hansen, Hertz and Quinodoz, who also gave an $O(n^3)$ algorithm for trees. In this talk we introduce another algorithm, whose running time is $O(n^2 lg ^3 n)$. We also present an improvement to our algorithm, which works for almost all labelled trees in time~$n^{1+o(1)}$.

If time permits, we will present an algorithm which solves the BWC problem for chordal graphs.

The celebrated Minimum Spanning Tree protocol of Gallager, Humblet and Spira has been very influential in the network algorithms arena. Although it is very intuitive it has proven to be a very hard protocol to verify correct. Despite many attempts, only two proofs were previously known, each roughly 180 pages long. We describe a new proof of correctness that is considerably shorter, and is the first to formalize the reasoning suggested in the original paper. The proof is based on a new abstraction that facilitates modular reasoning about the protocol. The talk will be self contained and will assume no prior knowledge of the subject matter.

Based on joint work with Benny Shimony.

One goal of Artificial Intelligence is to enable the creation of robust, fully autonomous agents that can coexist with us in the real world. Such agents will need to be able to learn, both in order to correct and circumvent their inevitable imperfections, and to keep up with a dynamically changing world. They will also need to be able to interact with one another, whether they share common goals, they pursue independent goals, or their goals are in direct conflict. This talk will present current research directions in machine learning, multiagent reasoning, and robotics, and will advocate their unification within concrete application domains. Ideally, new theoretical results in each separate area will inform practical implementations while innovations from concrete multiagent applications will drive new theoretical pursuits, and together these synergistic research approaches will lead us towards the goal of fully autonomous agents.