דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Parallel Repetition Theorem Reading Group: Parallel Repetition, Unique Games and Foams?
event speaker icon
פרלד הרשה (אונ' טקסס)
event date icon
יום רביעי, 3.12.2008, 12:00
event location icon
חדר 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.
[בחזרה לאינדקס האירועים]