Document Open Access Logo

On Fortification of Projection Games

Authors Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2015.497.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Parallel Repetition
  • Fortification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat. On Fortification of Projection Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 497-511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.497

Author Details

Amey Bhangale
Ramprasad Saptharishi
Girish Varma
Rakesh Venkat

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, May 1998. Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, January 1998. Google Scholar
  3. Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap*. Combinatorica, 26(5):495-519, 2006. Google Scholar
  4. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. Electronic Colloquium on Computational Complexity (ECCC), 21:95, 2014. To appear in STOC 2015. Google Scholar
  5. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633, 2014. Google Scholar
  6. Uriel Feige. On the success probability of the two provers in one-round proof systems. In Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual, pages 116-123, Jun 1991. Google Scholar
  7. Uriel Feige and Joe Kilian. Two prover protocols: low error at affordable rates. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 172-183, 1994. Google Scholar
  8. Lance Jeremy Fortnow. Complexity-theoretic aspects of interactive proof systems. PhD thesis, Massachusetts Institute of Technology, 1989. Google Scholar
  9. Thomas Holenstein. Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(1):141-172, 2009. Google Scholar
  10. Dana Moshkovitz. Parallel repetition from fortification. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 414-423, 2014. Google Scholar
  11. Dana Moshkovitz. Parallel repetition from fortification. http://people.csail.mit.edu/dmoshkov/papers/par-rep/final3.pdf, 2015.
  12. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math., 13(1):2-24, 2000. Google Scholar
  13. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871-1891, 2011. Google Scholar
  14. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. Google Scholar
  15. Ran Raz. A counterexample to strong parallel repetition. SIAM J. Comput., 40(3):771-777, June 2011. Google Scholar
  16. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pages 3-13, 2000. Google Scholar
  17. Oleg Verbitsky. Towards the parallel repetition conjecture. Theor. Comput. Sci., 157(2):277-282, May 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact