Prahladh Harsha (CS, University of Texas at Austin)
Wednesday, 3.12.2008, 12:00
In this reading group, we will study the parallel repetition theorem,
its connection to unique games and tiling in high dimensional spaces.
The parallel repetition theorem [Raz 1998] has been extremely useful
to compute the exact inapproximability of several optimization
problems. Two years ago, Holenstein gave a simplified proof of Raz's
theorem. Since then, there has been a flurry of activity in this area:
understanding the behavior for special type of 2-prover games
(projection, unique); its relation to unique games; why certain strong
forms of the repetition theorem are false; and interestingly enough,
why understanding repetition theorem requires an understanding of foams!!
We hope to cover all these (and more exciting topics) in this reading group.