Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

Events

Parallel Repetition Theorem Reading Group: Parallel Repetition, Unique Games and Foams?
event speaker icon
Prahladh Harsha (CS, University of Texas at Austin)
event date icon
Wednesday, 3.12.2008, 12:00
event location icon
Taub 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.
[Back to the index of events]