The Taub Faculty of Computer Science Events and Talks

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.