On Fortification of Projection Games

Randomization and Computation (RANDOM’15)
August, 2015

Bibtex

@InProceedings{BSVV15, author = {Amey Bhangale and Ramprasad Saptharishi and Girish Varma and Rakesh Venkat}, title = {{On Fortification of Projection Games}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {497--511}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5320}, URN = {urn:nbn:de:0030-drops-53204}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.497}, annote = {Keywords: Parallel Repetition, Fortification} }

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 1 and 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 2 guarantees) is necessary for obtaining the robustness required for fortification.