Header menu link for other important links
X
On fortification of projection games
A. Bhangale, R. Saptharishi, G. Varma,
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2015
Volume: 40
   
Pages: 497 - 511
Abstract
A recent result of Moshkovitz [10] 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 [10] 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 [11] of [10] 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. © Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969