loading...
Understanding Parallel Repetition Requires Understanding Foams
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.39Twenty-Second Annual IEEE Conference ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Uriel Feige, Weizmann Institute, Israel; Microsoft Research
Guy Kindler, Weizmann Institute, Israel
Ryan O'Donnell, Carnegia Mellon University, USA
Motivated by the study of Parallel Repetition and also by the Unique Games Conjecture, we investigate the value of the "Odd Cycle Games" under parallel repetition. Using tools from discrete harmonic analysis, we show that after d rounds on the cycle of length m, the value of the game is at most 1 - (1/m) \cdot \Omega(\sqrt d) (for d \leqslant m^2, say). This beats the natural barrier of 1 - \Theta (1/m)^2 \cdot d for Raz-style proofs [31, 21] (see [11]) and also the SDP bound of Feige-Lovasz [14, 17]; however, it just barely fails to have implications for Unique Games. On the other hand, we also show that improving our bound would require proving nontrivial lower bounds on the surface area of high-dimensional foams. Specifically, one would need to answer: What is the least surface area of a cell that tiles \mathbb{R}^d by the lattice \mathbb{Z}^{d}?
Citation:
Uriel Feige, Guy Kindler, Ryan O'Donnell, "Understanding Parallel Repetition Requires Understanding Foams," ccc, pp.179-192, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.