Previous Conferences & Workshops

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...