2006-2007 seminars

The Fast Johnson-Lindenstrauss Transorm was recently discovered by Ailon and Chazelle as a technique for performing fast dimension reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d, k^3\})$, where $k$ is the target lower dimension...

This talk is devoted to linear subspaces of $R^N$ on which $\ell_1$ and $\ell_2$-norms are closed to each other (up to the obvious normalizing factor $N^{1/2}$). Such ``sections'' are important e.g. in the theory of metric embeddings, and for many...

I will present Holenstein's (STOC 07) simplification of Raz's (STOC '95) proof of the parallel repetition theorem for two prover games. This theorem is a crucial component in many PCP constructions leading to tight hardness of approximation results...

Buy-at-bulk network design problems arise in telecommunication networks and related fields where economies of scale result in concave cost functions for purchasing bandwidth. A basic problem in this area is the following. We are given a graph G=(V,E...

This is joint work with Philipp Hertel Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and...

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since * reachability on grid graphs is logspace-equivalent to reachability in general...

In this talk we study the one-way multi-party communication model, in which each of the k parties speaks exactly once in its turn. For every fixed k, we prove a tight lower bound of Omega(n^(1/(k-1))) on the probabilistic communication complexity of...

This subject began in the late 1940s with the opus of Shannon [1948] and the short papers of Hamming [1950] and Golay [1949], followed a decade later by the powerful constructions of Bose-Chaudhuri-Hocquenghem and Reed-Solomon. A variety of...

Consensus clustering is the problem of aggregating a list of clusterings of ground data into one clustering. I will present new approximation algorithms for this problem, building on techniques used for ranking problems (described in my previous...

Program checking, program self-correcting and program self-testing were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by...