Previous Conferences & Workshops

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

In this talk I will discuss some recent results on the existence of certain unique models related to the Gross-Prasad conjecture. This is joint with Dipendra Prasad.

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