TR07-043 Authors: Uriel Feige, Guy Kindler, Ryan O'Donnell

Publication: 16th May 2007 14:16

Downloads: 971

Keywords:

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 \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$?