2008-2009 Seminars

The ``direct product code'' of a function $f$ gives its values on all $k$-tuples $(f(x_1),\dots,f(x_k))$. This basic construct underlies “hardness amplification” in cryptography, circuit complexity and PCPs. A recent breakthrough by Dinur and...

In this work we study the task of randomness extraction from sources which are distributed uniformly on an unknown algebraic variety. In other words, we are interested in constructing a function (an extractor) whose output is close to uniform even...

The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many natural families of chains are believed to exhibit cutoff, and yet establishing this fact is often extremely...

Recently, Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi introduced a natural metric on the space of dense graphs, and identified the completion of the metric space that arises. Independently and simultaneously, Janson, Riordan and I defined a...

Combinatorial arguments have played a crucial role in the investigation of several surprising phenomena in Information Theory. After a brief discussion of some of these results I will describe a recent example, based on joint work with Hassidim...

Getting the deterministic complexity closer to the best known randomized complexity is an important goal in algorithms and communication protocols. In this work, we investigate the case where instead of one input, the algorithm/protocol is given...

I will outline the general area of proof complexity, and its traditional problems. I will focus on less traditional ones, namely the complexity of proving identities over certain algebraic structures. The paradigmatic example is a system intended to...

The curvelet transform is a directional wavelet transform over R^n, originally due to Candes and Donoho (2002). It is used to analyze functions that have singularities along smooth surfaces. I demonstrate how this can lead to new quantum algorithms...

For a graph G , let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. We study the problem of bounding t(G) for graphs which do not contain a complete graph K_r on r vertices. This problem was posed twenty years...

I will outline the general area of proof complexity, and its traditional problems. I will focus on less traditional ones, namely the complexity of proving identities over certain algebraic structures. The paradigmatic example is a system intended to...