Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bhangale, Amey; Saptharishi, Ramprasad; Varma, Girish; Venkat, Rakesh https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-53204
URL:

; ; ;

On Fortification of Projection Games

pdf-format:


Abstract

A recent result of Moshkovitz [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 [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 l_1 and l_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 [Moshkovitz15] of [Moshkovitz14] with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular l_2 guarantees) is necessary for obtaining the robustness required for fortification.

BibTeX - Entry

@InProceedings{bhangale_et_al:LIPIcs:2015:5320,
  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}
}

Keywords: Parallel Repetition, Fortification
Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue date: 2015
Date of publication: 13.08.2015


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI