On approximability of satisfiable \(k\)-CSPs. I. (English) Zbl 07774393
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 976-988 (2022).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45, 3 (1998), May, 501-555. https://doi.org/10.1145/278298.278306 (Preliminary version in 33rd FOCS, 1992) 10.1145/278298.278306 · Zbl 1065.68570 |
| [2] | Sanjeev Arora and Shmuel Safra. 1998. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45, 1 (1998), Jan., 70-122. https://doi.org/10.1145/273865.273901 (Preliminary version in 33rd FOCS, 1992) 10.1145/273865.273901 · Zbl 0903.68076 |
| [3] | Per Austrin and Elchanan Mossel. 2009. Approximation resistant predicates from pairwise independence. Computational Complexity, 18, 2 (2009), 249-271. https://doi.org/10.1007/s00037-009-0272-6 10.1007/s00037-009-0272-6 · Zbl 1214.68172 |
| [4] | Amey Bhangale and Subhash Khot. 2021. Optimal Inapproximability of Satisfiable K-LIN over Non-Abelian Groups. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC). Association for Computing Machinery, New York, NY, USA. 1615-1628. isbn:9781450380539 https://doi.org/10.1145/3406325.3451003 10.1145/3406325.3451003 · Zbl 07765274 |
| [5] | Joshua Brakensiek and Venkatesan Guruswami. 2021. The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms, 17, 3 (2021), Article 27, jul, 35 pages. issn:1549-6325 https://doi.org/10.1145/3459668 10.1145/3459668 · Zbl 07475107 |
| [6] | Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer. 2022. An Invariance Principle for the Multi-slice, with Applications. In 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Denver, CO, USA. 228-236. https://doi.org/10.1109/FOCS52979.2021.00030 10.1109/FOCS52979.2021.00030 |
| [7] | Mark Braverman, Subhash Khot, and Dor Minzer. 2021. On Rich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science Conference (ITCS) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 185). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 27:1-27:20. isbn:978-3-95977-177-1 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ITCS.2021.27 10.4230/LIPIcs.ITCS.2021.27 |
| [8] | Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Berkeley, CA, USA. 319-330. https://doi.org/10.1109/FOCS.2017.37 10.1109/FOCS.2017.37 |
| [9] | Lars Engebretsen and Jonas Holmerin. 2005. Three-query PCPs with perfect completeness over non-Boolean domains. Random Structures & Algorithms, 27, 1 (2005), 46-75. https://doi.org/10.1002/rsa.20050 10.1002/rsa.20050 · Zbl 1161.68848 |
| [10] | Tomás Feder and Moshe Y. Vardi. 1998. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput., 28, 1 (1998), 57-104. https://doi.org/10.1137/S0097539794266766 10.1137/S0097539794266766 · Zbl 0914.68075 |
| [11] | Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43, 2 (1996), 268-292. https://doi.org/10.1145/226643.226652 10.1145/226643.226652 · Zbl 0882.68129 |
| [12] | Michel X. Goemans and David P. Williamson. 1995. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42, 6 (1995), 1115-1145. issn:0004-5411 https://doi.org/10.1145/227683.227684 10.1145/227683.227684 · Zbl 0885.68088 |
| [13] | Johan Håstad. 2001. Some optimal inapproximability results. J. ACM, 48, 4 (2001), July, 798-859. https://doi.org/10.1145/502090.502098 (Preliminary version in 29th STOC, 1997) 10.1145/502090.502098 · Zbl 1127.68405 |
| [14] | Johan Håstad and Subhash Khot. 2005. Query Efficient PCPs with Perfect Completeness. Theory of Computing, 1, 7 (2005), 119-148. https://doi.org/10.4086/toc.2005.v001a007 10.4086/toc.2005.v001a007 · Zbl 1213.68331 |
| [15] | Sangxia Huang. 2014. Approximation Resistance on Satisfiable Instances for Sparse Predicates. Theory of Computing, 10, 14 (2014), 359-388. https://doi.org/10.4086/toc.2014.v010a014 10.4086/toc.2014.v010a014 · Zbl 1319.68111 |
| [16] | Johan Håstad. 2014. On the NP-Hardness of Max-Not-2. SIAM J. Comput., 43, 1 (2014), 179-193. https://doi.org/10.1137/120882718 10.1137/120882718 · Zbl 1359.68105 |
| [17] | Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM symposium on Theory of computing (STOC). Association for Computing Machinery, New York, NY, USA. 767-775. https://doi.org/10.1145/509907.510017 10.1145/509907.510017 · Zbl 1192.68367 |
| [18] | Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. 2007. Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? SIAM J. Comput., 37, 1 (2007), 319-357. https://doi.org/10.1137/S0097539705447372 10.1137/S0097539705447372 · Zbl 1135.68019 |
| [19] | Elchanan Mossel. 2010. Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19, 6 (2010), 1713-1756. https://doi.org/10.1007/s00039-010-0047-x 10.1007/s00039-010-0047-x · Zbl 1205.60051 |
| [20] | Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. 2005. Noise stability of functions with low influences: invariance and optimality. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, Pittsburgh, PA, USA. 21-30. https://doi.org/10.1109/SFCS.2005.53 10.1109/SFCS.2005.53 · Zbl 1201.60031 |
| [21] | Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 14th annual ACM symposium on Theory of computing (STOC). Association for Computing Machinery, New York, NY, USA. 245-254. https://doi.org/10.1145/1374376.1374414 10.1145/1374376.1374414 · Zbl 1231.68142 |
| [22] | Prasad Raghavendra. 2009. Approximating np-hard problems efficient algorithms and their limits. Ph.D. thesis, University of Washington, Seattle, WA, USA. |
| [23] | Thomas J. Schaefer. 1978. The Complexity of Satisfiability Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, New York, NY, USA. 216-226. isbn:9781450374378 https://doi.org/10.1145/800133.804350 10.1145/800133.804350 · Zbl 1282.68143 |
| [24] | Linqing Tang. 2009. Conditional hardness of approximating satisfiable Max 3CSP-q. In International Symposium on Algorithms and Computation. Springer Berlin Heidelberg, Berlin, Heidelberg. 923-932. https://doi.org/10.1007/978-3-642-10631-6_93 10.1007/978-3-642-10631-6_93 · Zbl 1273.68154 |
| [25] | Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture. J. ACM, 67, 5 (2020), Article 30, Aug., 78 pages. issn:0004-5411 https://doi.org/10.1145/3402029 10.1145/3402029 · Zbl 1491.68128 |
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.
