Parallel Repetition From Fortification
The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games – “fortification” – and show that for fortified games, the value of the repeated...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/88557 https://orcid.org/0000-0002-5157-8086 |
| _version_ | 1826195054152122368 |
|---|---|
| author | Moshkovitz Aaronson, Dana Hadar |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Moshkovitz Aaronson, Dana Hadar |
| author_sort | Moshkovitz Aaronson, Dana Hadar |
| collection | MIT |
| description | The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games – “fortification” – and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and short. As corollaries, we obtain: (1) Starting from a PCP Theorem with soundness error bounded away from 1, we get a PCP with arbitrarily small constant soundness error. In particular, starting with the combinatorial PCP of Dinur, we get a combinatorial PCP with low error. The latter can be used for hardness of approximation as in the work of Hastad. (2) Starting from the work of the author and Raz, we get a projection PCP theorem with the smallest soundness error known today. The theorem yields nearly a quadratic improvement in the size compared to previous work. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. |
| first_indexed | 2024-09-23T10:06:09Z |
| format | Article |
| id | mit-1721.1/88557 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:06:09Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/885572022-09-26T15:42:14Z Parallel Repetition From Fortification Moshkovitz Aaronson, Dana Hadar Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Moshkovitz Aaronson, Dana Hadar Moshkovitz Aaronson, Dana Hadar The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games – “fortification” – and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and short. As corollaries, we obtain: (1) Starting from a PCP Theorem with soundness error bounded away from 1, we get a PCP with arbitrarily small constant soundness error. In particular, starting with the combinatorial PCP of Dinur, we get a combinatorial PCP with low error. The latter can be used for hardness of approximation as in the work of Hastad. (2) Starting from the work of the author and Raz, we get a projection PCP theorem with the smallest soundness error known today. The theorem yields nearly a quadratic improvement in the size compared to previous work. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. National Science Foundation (U.S.) (Grant 1218547) 2014-08-07T12:17:54Z 2014-08-07T12:17:54Z 2014-10 Article http://purl.org/eprint/type/ConferencePaper 0272-5428 INSPEC Accession No.: 14819560 http://hdl.handle.net/1721.1/88557 Moshkovitz, Hadar Dana. Parallel Repetition from Fortification. The 55th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, October 18-21, 2014. pp. 414-423. https://orcid.org/0000-0002-5157-8086 en_US http://dx.doi.org/10.1109/FOCS.2014.51 Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Moshkovitz |
| spellingShingle | Moshkovitz Aaronson, Dana Hadar Parallel Repetition From Fortification |
| title | Parallel Repetition From Fortification |
| title_full | Parallel Repetition From Fortification |
| title_fullStr | Parallel Repetition From Fortification |
| title_full_unstemmed | Parallel Repetition From Fortification |
| title_short | Parallel Repetition From Fortification |
| title_sort | parallel repetition from fortification |
| url | http://hdl.handle.net/1721.1/88557 https://orcid.org/0000-0002-5157-8086 |
| work_keys_str_mv | AT moshkovitzaaronsondanahadar parallelrepetitionfromfortification |