ECCC-Report TR07-043https://eccc.weizmann.ac.il/report/2007/043Comments and Revisions published for TR07-043en-usWed, 16 May 2007 14:16:03 +0300
Paper TR07-043
| Understanding Parallel Repetition Requires Understanding Foams |
Uriel Feige,
Guy Kindler,
Ryan O'Donnell
https://eccc.weizmann.ac.il/report/2007/043Motivated 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 \Omegat(\sqrt{d})$
(for $d \leq m^2$, say). <br><br>This beats the natural barrier of $1 -
\Theta(1/m)^2 \cdot d$ for Raz-style proofs~\cite{Raz98,Hol06}
(see~\cite{Fei95}) and also the SDP bound of
Feige-Lov{\'a}sz~\cite{FL92,GW95}; 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
$\R^d$ by the lattice $\Z^d$?
Wed, 16 May 2007 14:16:03 +0300https://eccc.weizmann.ac.il/report/2007/043