Reading Group: Parallel Repetiion, Unique Games and Foams? - Winter 2008-09

Time : Wed 1:30-3:30pm
Location : Taub 201
Organizer : (<firstname> AT cs DOT technion DOT ac DOT il)
Homepage: http://www.cs.technion.ac.il/~prahladh/teaching/08winter/

Reading Group Announcement

Group Meetings

1. Meeting 1 (Dec 3): Introduction, repetition theorem (Presenter: Prahladh Harsha)
   Administrivia, Raz's parallel repetition theorem, Overview of Raz's proof (part 1).
   Ref: [Raz1, Hol].
   
   
2. Meeting 2 (Dec 10): Proof of repetition theorem (part 2) (Presenter: Prahladh Harsha)
   Ref: [Raz1, Hol, Rao].
   Note: Meeting in Taub 337, 2:40-4:00pm (due to Haifa University/Technion Combinatorics Seminar)
   
   
3. Meeting 3 (Dec 31): Proof of repetiton theorem (part 3) (Presenter: Prahladh Harsha)
   Ref: [Raz1, Hol, Rao].
   
   
4. Meeting 4 (Jan 7): Limitations of derandomizing parallel repetition games (Presenter: Ronen Shaltiel)
   Ref: [FK].
   
   *** Jan 14: Meeting Cancelled in view of Hendrik Lenstra's talk at Haifa University. ***
   
   
5. Meeting 5 (Jan 21): Counterexample for strong repetition theorem (Presenter: Enav Wienreb)
   Ref: [Raz2].
   
   
6. Meeting 6 (Jan 28): Rounding parallel repetition of unique games (Presenter: Noa Elgrabli)
   Ref: [BHHRS].
   
   
7. Meeting 7 (Feb 4): Understanding repetition requires requiring foams. (Presenter: Prahladh Harsha)
   Ref: [FKO].
   
   
8. Meeting 8 (Feb 11): Spherical cubes, Rounding and Tiling in high-dimensional spaces. (Presenter: Yuval Rabani)
   Ref: [GORW].
   
   

References

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

1. [BHHRS] Boaz Barak, Moritz Hardt, Ishay Haviv, Oded Regev and David Steurer: Rounding Parallel Repetitions of Unique Games, FOCS 2008.
2. [FK] Uriel Feige, Joe Kilian: Impossibility results for recycling random bits in two-prover proof systems, STOC 1995.
3. [FKO] Uriel Feige, Guy Kindler, Ryan O'Donnell: Understanding Parallel Repetition Requires Understanding Foams, IEEE Conference on Computational Complexity 2007.
4. [Hol] Thomas Holenstein: Parallel repetition: simplifications and the no-signaling case, STOC 2007.
5. [GORW] Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson: Spherical Cubes and Rounding in High Dimensions, FOCS 2008.
6. [Rao] Anup Rao: Parallel Repetition in Projection Games and a Concentration Bound, STOC 2008
7. [Raz1] Ran Raz: "A Parallel Repetition Theorem". SIAM J. Comput. 27(3): 763-803 (1998).
8. [Raz2] Ran Raz: A counterexample to Strong parallel repetiton, FOCS 2008.

This page has been accessed at least times since Dec 1, 2008.

Prahladh Harsha