Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Foams:
TR07-043 | 7th May 2007
Uriel Feige, Guy Kindler, Ryan O'Donnell

Understanding Parallel Repetition Requires Understanding Foams

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

ISSN 1433-8092 | Imprint