Guy Kindler
Weizmann Institute
December 26, 2007
Title: Understanding parallel repetition
requires understanding foams
Abstract:
The parallel repetition theorem, proven by Raz in 1995, is a fundamental
result that in addition to its philosophical appeal, plays a key role in
complexity theory. The theorem studies the behavior of success
probabilities of two prover games, when many copies of such a game are
played in parallel. It shows that the success probability decreases
exponentially in the number of repetitions, but the parameters given by
the theorem do not seem tight. It is natural to ask what are the best
parameters for which the theorem holds, and improving them would have
complexity theoretic implications.
This talk describes an attempt to improve the parameters in a very
special case of the parallel repetition theorem. Our attempt had only
limited success, but it turns out that the reason we got stuck was that
the following seemingly hard question from the geometry of "foams" was
hidden in the special case that we were trying to solve: What is the
least surface area of a cell that tiles R^d by the lattice Z^d? Very
little about this foam problem is known. It is interesting to see such a
geometric question encoded inside the problem of parallel repetition in
two prover games.
This is joint work with Uri Feige (Microsoft) and Ryan O'Donnell (CMU).