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)

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].


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 several times since Dec 1, 2008.

Prahladh Harsha
Valid HTML 4.01! Valid CSS!