Document Open Access Logo

Imperfect Gaps in Gap-ETH and PCPs

Authors Mitali Bafna, Nikhil Vyas

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2019.32.pdf
  • Filesize: 0.52 MB
  • 19 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Complexity theory and logic
Keywords
  • PCP
  • Gap-ETH
  • Hardness of Approximation

Metrics

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

Abstract

We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a way to transform a PCP with imperfect completeness to one with perfect completeness, when the initial gap is a constant. We show that PCP_{c,s}[r,q] subseteq PCP_{1,s'}[r+O(1),q+O(r)] for c-s=Omega(1) which in turn implies that one can convert imperfect completeness to perfect in linear-sized PCPs for NP with a O(log n) additive loss in the query complexity q. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs, (when completeness is not 1) analogous to questions studied in parallel repetition [Anup Rao, 2011] and pseudorandomness [David Gillman, 1998] and might be of independent interest.
We also investigate the time-complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. MAX 3SAT(1-epsilon,1-delta), delta > epsilon has 2^{o(n)} algorithms if and only if MAX 3SAT(1,1-delta) has 2^{o(n)} algorithms. We also relate the time complexities of these two problems in a more fine-grained way to show that T_2(n) <= T_1(n(log log n)^{O(1)}), where T_1(n),T_2(n) denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness respectively.

Cite As Get BibTex

Mitali Bafna and Nikhil Vyas. Imperfect Gaps in Gap-ETH and PCPs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.32

Author Details

Mitali Bafna
  • Harvard University, Cambridge, MA, USA
Nikhil Vyas
  • MIT, Cambridge, MA, USA

Funding

  • Bafna, Mitali: Supported by NSF Grant CCF-1565641 and CCF-1715187.
  • Vyas, Nikhil: Supported by NSF Grant CCF-1741615.

Acknowledgements

We would like to thank our advisors Madhu Sudan and Ryan Williams for helpful discussions. We are also grateful to all the reviewers, for detailed comments on the paper.

References

  1. Divesh Aggarwal and Noah Stephens-Davidowitz. (Gap/S)ETH hardness of SVP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 228-238, 2018. Google Scholar
  2. Benny Applebaum. Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 836-847, 2017. Google Scholar
  3. 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, 1998. URL: https://doi.org/10.1145/278298.278306.
  4. Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Hardness amplification for entangled games via anchoring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 303-316, 2017. Google Scholar
  5. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J. Comput., 27(3):804-915, 1998. URL: https://doi.org/10.1137/S0097539796302531.
  6. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 320-329, 2013. Google Scholar
  7. Eli Ben-Sasson and Madhu Sudan. Short PCPs with Polylog Query Complexity. SIAM J. Comput., 38(2):551-607, 2008. URL: https://doi.org/10.1137/050646445.
  8. Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 17:1-17:15, 2018. Google Scholar
  9. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 743-754, 2017. Google Scholar
  10. Siu On Chan. Approximation resistance from pairwise independent subgroups. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 447-456, 2013. Google Scholar
  11. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. URL: https://doi.org/10.1145/1236457.1236459.
  12. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.
  13. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376-389, 2018. Google Scholar
  14. Irit Dinur and Pasin Manurangsi. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 36:1-36:20, 2018. Google Scholar
  15. David Gillman. A Chernoff Bound for Random Walks on Expander Graphs. SIAM J. Comput., 27(4):1203-1220, 1998. URL: https://doi.org/10.1137/S0097539794268765.
  16. Oded Goldreich. A Sample of Samplers - A Computational Perspective on Sampling (survey). Electronic Colloquium on Computational Complexity (ECCC), 4(20), 1997. URL: http://eccc.hpi-web.de/eccc-reports/1997/TR97-020/index.html.
  17. Venkatesan Guruswami and Luca Trevisan. The Complexity of Making Unique Choices: Approximating 1-in- k SAT. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, pages 99-110, 2005. Google Scholar
  18. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: https://doi.org/10.1145/502090.502098.
  19. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  20. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767-775, 2002. Google Scholar
  21. Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 78:1-78:15, 2017. Google Scholar
  22. Anup Rao. Parallel Repetition in Projection Games and a Concentration Bound. SIAM J. Comput., 40(6):1871-1891, 2011. URL: https://doi.org/10.1137/080734042.
  23. Ran Raz. A Parallel Repetition Theorem. SIAM J. Comput., 27(3):763-803, 1998. URL: https://doi.org/10.1137/S0097539795280895.
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