Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-069 | 25th May 2015 17:26

#### On Fortification of Projection Games

Revision #1
Authors: Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat
Accepted on: 25th May 2015 17:26
Keywords:

Abstract:

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel repetition. In this paper, we provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both $\ell_1$ and $\ell_2$ guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters (the latter is also the construction used in an independent update \cite{Moshkovitz15} of \cite{Moshkovitz14} with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular $\ell_2$ guarantees) is necessary for obtaining the robustness required for fortification.

Changes to previous version:

Incorporated a subtlety in using the fortification technique of [Mos14] for parallel repetition of general games.

### Paper:

TR15-069 | 21st April 2015 21:21

#### On Fortification of General Games

TR15-069
Authors: Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat
Publication: 21st April 2015 21:36
A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel repetition. In this paper, we provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both $\ell_1$ and $\ell_2$ guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters (the latter is also the construction used in an independent update \cite{Moshkovitz15} of \cite{Moshkovitz14} with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular $\ell_2$ guarantees) is necessary for obtaining the robustness required for fortification. Furthermore, we show that this can yield a similar parallel repetition theorem for robust general games and not just robust projection games on bi-regular graphs.