יום רביעי, 3.12.2008, 12:00
חדר 201, בניין טאוב למדעי המחשב
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.