• Calendar

November 6, Tuesday
12:00 – 14:00

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.