Time : Wed 1:30-3:30pm
Location: Taub 201
Organizer :
Homepage:
http:/www.cs.technion.ac.il/~prahladh/teaching/08winter/
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 simplified Raz's proof of the repetition 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.
| Prahladh Harsha |
|