Imperfect gaps in gap-ETH and PCPs. (English) Zbl 07564432
Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 32, 19 p. (2019).
Summary: 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 \(\text{PCP}_{c,s}[r,q]\subseteq \text{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 [A. Rao, SIAM J. Comput. 40, No. 6, 1871–1891 (2011; Zbl 1235.68078)] and pseudorandomness [D. Gillman, SIAM J. Comput. 27, No. 4, 1203–1220 (1998; Zbl 0911.60016)] 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-\varepsilon,1-\delta)\), \(\delta>\varepsilon\) 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)\le 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.
For the entire collection see [Zbl 1414.68009].
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-\varepsilon,1-\delta)\), \(\delta>\varepsilon\) 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)\le 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.
For the entire collection see [Zbl 1414.68009].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | 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. |
| [2] | 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. doi:10.1145/278298.278306. · Zbl 1065.68570 · doi:10.1145/278298.278306 |
| [3] | 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. · Zbl 1370.81013 |
| [4] | Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability-Towards Tight Results. · Zbl 0912.68041 |
| [5] | SIAM J. Comput., 27(3):804-915, 1998. doi:10.1137/ S0097539796302531. · Zbl 0912.68041 · doi: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. |
| [7] | Eli Ben-Sasson and Madhu Sudan. Short PCPs with Polylog Query Complexity. SIAM J. Comput., 38(2):551-607, 2008. doi:10.1137/050646445. · Zbl 1172.68025 · doi: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. · Zbl 1499.68150 |
| [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. |
| [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. · Zbl 1293.68163 |
| [11] | Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. doi:10.1145/ 1236457.1236459. · Zbl 1292.68074 · doi: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. · Zbl 1429.68076 |
| [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. · Zbl 1462.68068 |
| [15] | David Gillman. A Chernoff Bound for Random Walks on Expander Graphs. SIAM J. Comput., 27(4):1203-1220, 1998. doi:10.1137/S0097539794268765. · Zbl 0911.60016 · doi: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. · Zbl 1343.68297 |
| [17] | Venkatesan Guruswami and Luca Trevisan. The Complexity of Making Unique Choices: Ap-proximating 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. · Zbl 1142.68611 |
| [18] | Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. doi:10.1145/502090.502098. · Zbl 1127.68405 · doi: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. doi:10.1006/jcss.2000.1727. · Zbl 0990.68079 · doi: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. · Zbl 1192.68367 |
| [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. · Zbl 1441.68048 |
| [22] | Anup Rao. Parallel Repetition in Projection Games and a Concentration Bound. SIAM J. Comput., 40(6):1871-1891, 2011. doi:10.1137/080734042. · Zbl 1235.68078 · doi:10.1137/080734042 |
| [23] | Ran Raz. A Parallel Repetition Theorem. SIAM J. Comput., 27(3):763-803, 1998. doi: 10.1137/S0097539795280895. · Zbl 0911.68082 · doi:10.1137/S0097539795280895 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
