Title : Understanding Parallel Repetition Requires Understanding Foams.
Speaker: Ryan O’Donnell
When : March 8th, 4:30-5:30pm
Where : PPB 300
Abstract:
Motivated by important problems in complexity theory (the Unique Games Conjecture) and the foundations of quantum mechanics (QM vs. local hidden variable theories), we investigate the best parameters obtainable in the Parallel Repetition Theorem.
Unfortunately, we don’t get very far.
But, it’s because we get blocked by the following seemingly very hard question from the geometry of “foams”: 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 so vexing that I will offer monetary rewards for baby steps of progress.
This is joint work with Uri Feige (Microsoft Research/Weizmann) and Guy Kindler (Weizmann).
