Approximate graph colouring and the hollow shadow. (English) Zbl 07844617
Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 623-631 (2023).
MSC:
| 68Qxx | Theory of computing |
Keywords:
Diophantine equations; Sherali-Adams linear programming relaxations; affine Integer programming relaxations; approximate graph colouring; promise constraint satisfactionReferences:
| [1] | Richard P Anstee. 1982. Properties of a class of (0, 1)-matrices covering a given matrix. Canadian Journal of Mathematics, 34, 2 (1982), 438-453. https://doi.org/10.4153/CJM-1982-029-3 10.4153/CJM-1982-029-3 · Zbl 0442.05012 |
| [2] | Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis. 2006. Proving Integrality Gaps without Knowing the Linear Program. Theory Comput., 2, 2 (2006), 19-51. https://doi.org/10.4086/toc.2006.v002a002 10.4086/toc.2006.v002a002 · Zbl 1213.68306 |
| [3] | Kristina Asimi and Libor Barto. 2021. Finitely Tractable Promise Constraint Satisfaction Problems. In Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21) (LIPIcs, Vol. 202). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 11:1-11:16. https://doi.org/10.4230/LIPIcs.MFCS.2021.11 10.4230/LIPIcs.MFCS.2021.11 · Zbl 07724184 |
| [4] | Albert Atserias and Víctor Dalmau. 2022. Promise Constraint Satisfaction and Width. In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22). 1129-1153. https://doi.org/10.1137/1.9781611977073.48 arXiv:2107.05886. 10.1137/1.9781611977073.48 · Zbl 07883629 |
| [5] | Per Austrin, Venkatesan Guruswami, and Johan Håstad. 2017. (2+∊ )-Sat Is NP-hard. SIAM J. Comput., 46, 5 (2017), 1554-1573. https://doi.org/10.1137/15M1006507 eccc:2013/159. 10.1137/15M1006507 · Zbl 1476.68188 |
| [6] | Libor Barto. 2016. The collapse of the bounded width hierarchy. J. Log. Comput., 26, 3 (2016), 923-943. https://doi.org/10.1093/logcom/exu070 10.1093/logcom/exu070 · Zbl 1353.68107 |
| [7] | Libor Barto, Diego Battistelli, and Kevin M. Berg. 2021. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21) (LIPIcs, Vol. 187). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 10:1-10:16. https://doi.org/10.4230/LIPIcs.STACS.2021.10 arXiv:2010.04623. 10.4230/LIPIcs.STACS.2021.10 |
| [8] | Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. 2021. Algebraic approach to promise constraint satisfaction. J. ACM, 68, 4 (2021), 28:1-28:66. https://doi.org/10.1145/3457606 arXiv:1811.00970. 10.1145/3457606 · Zbl 1499.68140 |
| [9] | Libor Barto and Marcin Kozik. 2014. Constraint Satisfaction Problems Solvable by Local Consistency Methods. J. ACM, 61, 1 (2014), https://doi.org/10.1145/2556646 Article No. 3 10.1145/2556646 · Zbl 1295.68126 |
| [10] | Libor Barto and Marcin Kozik. 2022. Combinatorial Gap Theorem and Reductions between Promise CSPs. In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22). 1204-1220. https://doi.org/10.1137/1.9781611977073.50 arXiv:2107.09423. 10.1137/1.9781611977073.50 · Zbl 1482.68160 |
| [11] | Christoph Berkholz and Martin Grohe. 2017. Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). SIAM, 327-339. https://doi.org/10.1137/1.9781611974782.21 arXiv:1607.04287. 10.1137/1.9781611974782.21 · Zbl 1410.68153 |
| [12] | Amey Bhangale and Subhash Khot. 2021. Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. In Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC’21). ACM, 1615-1628. https://doi.org/10.1145/3406325.3451003 arXiv:2009.02815. 10.1145/3406325.3451003 · Zbl 07765274 |
| [13] | Amey Bhangale, Subhash Khot, and Don Minzer. 2022. On Inapproximability of Satisfiable k-CSPs: I.. In Proc. 54th Annual ACM Symposium on Theory of Computing (STOC’22). ACM, 976-988. https://doi.org/10.1145/3519935.3520028 10.1145/3519935.3520028 · Zbl 07774393 |
| [14] | Joshua Brakensiek and Venkatesan Guruswami. 2016. New Hardness Results for Graph and Hypergraph Colorings. In Proc. 31st Conference on Computational Complexity (CCC’16) (LIPIcs, Vol. 50). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14:1-14:27. https://doi.org/10.4230/LIPIcs.CCC.2016.14 10.4230/LIPIcs.CCC.2016.14 · Zbl 1380.68190 |
| [15] | Joshua Brakensiek and Venkatesan Guruswami. 2019. An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19). 436-455. https://doi.org/10.1137/1.9781611975482.28 arXiv:1807.05194. 10.1137/1.9781611975482.28 · Zbl 1431.68043 |
| [16] | Joshua Brakensiek and Venkatesan Guruswami. 2021. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput., 50, 6 (2021), 1663-1700. https://doi.org/10.1137/19M128212X arXiv:1704.01937. 10.1137/19M128212X · Zbl 1494.68094 |
| [17] | Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. 2021. Conditional Dichotomy of Boolean Ordered Promise CSPs. In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP’21) (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 37:1-37:15. https://doi.org/10.4230/LIPIcs.ICALP.2021.37 arXiv:2102.11854. 10.4230/LIPIcs.ICALP.2021.37 · Zbl 1494.68094 |
| [18] | Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. 2020. The power of the combined basic LP and affine relaxation for promise CSPs. SIAM J. Comput., 49 (2020), 1232-1248. https://doi.org/10.1137/20M1312745 arXiv:1907.04383. 10.1137/20M1312745 · Zbl 1496.68255 |
| [19] | Alex Brandts, Marcin Wrochna, and Stanislav Živný. 2021. The complexity of promise SAT on non-Boolean domains. ACM Trans. Comput. Theory, 13, 4 (2021), 26:1-26:20. https://doi.org/10.1145/3470867 arXiv:1911.09065. 10.1145/3470867 · Zbl 1495.68157 |
| [20] | Gábor Braun, Sebastian Pokutta, and Daniel Zink. 2015. Inapproximability of Combinatorial Problems via Small LPs and SDPs. In Proc. 47th Annual ACM on Symposium on Theory of Computing (STOC’15). ACM, 107-116. https://doi.org/10.1145/2746539.2746550 10.1145/2746539.2746550 · Zbl 1321.90098 |
| [21] | Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer. 2021. An Invariance Principle for the Multi-slice, with Applications. In Proc. 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS’21). IEEE, 228-236. https://doi.org/10.1109/FOCS52979.2021.00030 10.1109/FOCS52979.2021.00030 |
| [22] | Mark Braverman, Subhash Khot, and Dor Minzer. 2021. On Rich 2-to-1 Games. In Proc. 12th Innovations in Theoretical Computer Science Conference (ITCS’21) (LIPIcs, Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 27:1-27:20. https://doi.org/10.4230/LIPIcs.ITCS.2021.27 10.4230/LIPIcs.ITCS.2021.27 |
| [23] | Richard A. Brualdi and Geir Dahl. 2003. Matrices of zeros and ones with given line sums and a zero block. Linear Algebra Appl., 371 (2003), 191-207. issn:0024-3795 https://doi.org/10.1016/S0024-3795(03)00429-4 10.1016/S0024-3795(03)00429-4 · Zbl 1019.05018 |
| [24] | R. A. Brualdi and G. Dahl. 2007. Constructing (0,1)-matrices with given line sums and certain fixed zeros. In Advances in discrete tomography and its applications. Birkhäuser Boston, Boston, MA, 113-123. https://doi.org/10.1007/978-0-8176-4543-4_6 10.1007/978-0-8176-4543-4_6 · Zbl 1131.65037 |
| [25] | Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17). 319-330. issn:0272-5428 https://doi.org/10.1109/FOCS.2017.37 arXiv:1703.03021. 10.1109/FOCS.2017.37 |
| [26] | Silvia Butti and Víctor Dalmau. 2021. Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem. In Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21) (LIPIcs, Vol. 202). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 27:1-27:19. https://doi.org/10.4230/LIPIcs.MFCS.2021.27 arXiv:2107.02956. 10.4230/LIPIcs.MFCS.2021.27 · Zbl 07724200 |
| [27] | Siu On Chan. 2016. Approximation Resistance from Pairwise-Independent Subgroups. J. ACM, 63, 3 (2016), 27:1-27:32. https://doi.org/10.1145/2873054 10.1145/2873054 · Zbl 1426.68115 |
| [28] | Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. 2016. Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM, 63, 4 (2016), 34:1-34:22. https://doi.org/10.1145/2811255 10.1145/2811255 · Zbl 1394.68170 |
| [29] | Wei Chen, Yanfang Mo, Li Qiu, and Pravin Varaiya. 2016. Constrained (0,1)-matrix completion with a staircase of fixed zeros. Linear Algebra Appl., 510 (2016), 171-185. issn:0024-3795 https://doi.org/10.1016/j.laa.2016.08.020 10.1016/j.laa.2016.08.020 · Zbl 1352.05178 |
| [30] | William Y. C. Chen. 1992. Integral matrices with given row and column sums. J. Combin. Theory Ser. A, 61, 2 (1992), 153-172. issn:0097-3165 https://doi.org/10.1016/0097-3165(92)90015-M 10.1016/0097-3165(92)90015-M · Zbl 0773.05027 |
| [31] | Lorenzo Ciardo and Stanislav Živný. 2022. Approximate Graph Colouring and the Hollow Shadow. arXiv:2211.03168. |
| [32] | Lorenzo Ciardo and Stanislav Živný. 2023. Approximate Graph Colouring and Crystals. In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23). 2256-2267. https://doi.org/10.1137/1.9781611977554.ch86 arXiv:2210.08293. 10.1137/1.9781611977554.ch86 · Zbl 07848046 |
| [33] | Lorenzo Ciardo and Stanislav Živný. 2023. CLAP: A New Algorithm for Promise CSPs. SIAM J. Comput., 52, 1 (2023), 1-37. https://doi.org/10.1137/22M1476435 arXiv:2107.05018. 10.1137/22M1476435 · Zbl 07672223 |
| [34] | Lorenzo Ciardo and Stanislav Živný. 2023. Hierarchies of minion tests for PCSPs through tensors. In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23). 568-580. https://doi.org/10.1137/1.9781611977554.ch25 arXiv:2207.02277. 10.1137/1.9781611977554.ch25 · Zbl 07847985 |
| [35] | Adam Ó Conghaile. 2022. Cohomology in Constraint Satisfaction and Structure Isomorphism. In Proc. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS’22) (LIPIcs, Vol. 241). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 75:1-75:16. https://doi.org/10.4230/LIPIcs.MFCS.2022.75 arXiv:2206.15253. 10.4230/LIPIcs.MFCS.2022.75 · Zbl 07893113 |
| [36] | Geir Dahl. 2008. Transportation matrices with staircase patterns and majorization. Linear Algebra Appl., 429, 7 (2008), 1840-1850. issn:0024-3795 https://doi.org/10.1016/j.laa.2008.05.019 10.1016/j.laa.2008.05.019 · Zbl 1251.15022 |
| [37] | Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. 2018. On non-optimally expanding sets in Grassmann graphs. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18). ACM, 940-951. https://doi.org/10.1145/3188745.3188806 10.1145/3188745.3188806 · Zbl 1429.68077 |
| [38] | Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. 2018. Towards a proof of the 2-to-1 games conjecture? In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18). ACM, 376-389. https://doi.org/10.1145/3188745.3188804 10.1145/3188745.3188804 · Zbl 1429.68076 |
| [39] | Irit Dinur, Elchanan Mossel, and Oded Regev. 2009. Conditional Hardness for Approximate Coloring. SIAM J. Comput., 39, 3 (2009), 843-873. https://doi.org/10.1137/07068062X 10.1137/07068062X · Zbl 1192.68317 |
| [40] | 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 |
| [41] | D. R. Fulkerson. 1960. Zero-one matrices with zero trace. Pacific J. Math., 10 (1960), 831-836. issn:0030-8730 https://doi.org/10.2140/pjm.1960.10.831 10.2140/pjm.1960.10.831 · Zbl 0096.00703 |
| [42] | M. R. Garey and David S. Johnson. 1976. The Complexity of Near-Optimal Graph Coloring. J. ACM, 23, 1 (1976), 43-49. https://doi.org/10.1145/321921.321926 10.1145/321921.321926 · Zbl 0322.05111 |
| [43] | Mrinalkanti Ghosh and Madhur Tulsiani. 2018. From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems. Theory Comput., 14, 1 (2018), 1-33. https://doi.org/10.4086/toc.2018.v014a010 10.4086/toc.2018.v014a010 · Zbl 1394.68178 |
| [44] | Venkatesan Guruswami and Sanjeev Khanna. 2004. On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM Journal on Discrete Mathematics, 18, 1 (2004), 30-40. https://doi.org/10.1137/S0895480100376794 10.1137/S0895480100376794 · Zbl 1087.68071 |
| [45] | Venkatesan Guruswami and Sai Sandeep. 2020. d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP’20) (LIPIcs, Vol. 168). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 62:1-62:12. https://doi.org/10.4230/LIPIcs.ICALP.2020.62 10.4230/LIPIcs.ICALP.2020.62 · Zbl 07650082 |
| [46] | C.C Harner and R.C Entringer. 1972. Arc Colorings of Digraphs. J. Comb. Theory, Ser. B, 13, 3 (1972), 219-225. issn:0095-8956 https://doi.org/10.1016/0095-8956(72)90057-3 10.1016/0095-8956(72)90057-3 · Zbl 0231.05105 |
| [47] | Pavol Hell and Jaroslav Nešetřil. 2004. Graphs and homomorphisms (Oxford Lecture Series in Mathematics and its Applications, Vol. 28). OUP Oxford. · Zbl 1062.05139 |
| [48] | Sangxia Huang. 2013. Improved Hardness of Approximating Chromatic Number. In Proc. 16th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques and the 17th International Workshop on Randomization and Computation (APPROX-RANDOM’13). Springer, 233-243. isbn:978-3-642-40328-6 https://doi.org/10.1007/978-3-642-40328-6_17 arXiv:1301.5216. 10.1007/978-3-642-40328-6_17 · Zbl 1407.68195 |
| [49] | Charles R. Johnson and David P. Stanford. 2000. Patterns that allow given row and column sums. Linear Algebra Appl., 311, 1-3 (2000), 97-105. issn:0024-3795 https://doi.org/10.1016/S0024-3795(00)00071-9 10.1016/S0024-3795(00)00071-9 · Zbl 0947.05051 |
| [50] | Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Proc. Complexity of Computer Computations. 85-103. https://doi.org/10.1007/978-1-4684-2001-2_9 10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [51] | Ken-ichi Kawarabayashi and Mikkel Thorup. 2017. Coloring 3-Colorable Graphs with Less than n^1/5 Colors. J. ACM, 64, 1 (2017), 4:1-4:23. https://doi.org/10.1145/3001582 10.1145/3001582 · Zbl 1426.05166 |
| [52] | Sanjeev Khanna, Nathan Linial, and Shmuel Safra. 2000. On the Hardness of Approximating the Chromatic Number. Comb., 20, 3 (2000), 393-415. https://doi.org/10.1007/s004930070013 10.1007/s004930070013 · Zbl 0964.68065 |
| [53] | Subhash Khot. 2001. Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. In Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’01). IEEE Computer Society, 600-609. isbn:0-7695-1390-5 https://doi.org/10.1109/SFCS.2001.959936 10.1109/SFCS.2001.959936 |
| [54] | Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proc. 34th Annual ACM Symposium on Theory of Computing (STOC’02). ACM, 767-775. https://doi.org/10.1145/509907.510017 10.1145/509907.510017 · Zbl 1192.68367 |
| [55] | Subhash Khot, Dor Minzer, and Muli Safra. 2017. On independent sets, 2-to-2 games, and Grassmann graphs. In Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC’17). ACM, 576-589. https://doi.org/10.1145/3055399.3055432 10.1145/3055399.3055432 · Zbl 1370.68130 |
| [56] | Subhash Khot, Dor Minzer, and Muli Safra. 2018. Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. In Proc. 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS’18). IEEE Computer Society, 592-601. https://doi.org/10.1109/FOCS.2018.00062 10.1109/FOCS.2018.00062 · Zbl 07690461 |
| [57] | Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. 2017. Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC’17). ACM, 590-603. https://doi.org/10.1145/3055399.3055438 10.1145/3055399.3055438 · Zbl 1370.68133 |
| [58] | Andrei Krokhin and Jakub Opršal. 2022. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News, 9, 3 (2022), 30-59. arXiv:2208.13538. |
| [59] | Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. 2022. Topology and adjunction in promise constraint satisfaction. SIAM J. Comput., arXiv:2003.11351. · Zbl 07672224 |
| [60] | Jean B. Lasserre. 2002. An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs. SIAM J. Optim., 12, 3 (2002), 756-769. https://doi.org/10.1137/S1052623400380079 10.1137/S1052623400380079 · Zbl 1007.90046 |
| [61] | Monique Laurent. 2003. A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Math. Oper. Res., 28, 3 (2003), 470-496. https://doi.org/10.1287/moor.28.3.470.16391 10.1287/moor.28.3.470.16391 · Zbl 1082.90084 |
| [62] | James R. Lee, Prasad Raghavendra, and David Steurer. 2015. Lower Bounds on the Size of Semidefinite Programming Relaxations. In Proc. 47th Annual ACM on Symposium on Theory of Computing (STOC’15). ACM, 567-576. https://doi.org/10.1145/2746539.2746599 10.1145/2746539.2746599 · Zbl 1321.90099 |
| [63] | Tamio-Vesa Nakajima and Stanislav Živný. 2022. Linearly Ordered Colourings of Hypergraphs. In Proc. 49th International Colloquium on Automata, Languages, and Programming (ICALP’22) (LIPIcs, Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 128:1-128:18. https://doi.org/10.4230/LIPIcs.ICALP.2022.128 arXiv:2204.05628. 10.4230/LIPIcs.ICALP.2022.128 · Zbl 07870338 |
| [64] | Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology. http://www.cds.caltech.edu/ doyle/hot/thesis.pdf |
| [65] | Thomas Schaefer. 1978. The complexity of satisfiability problems. In Proc. 10th Annual ACM Symposium on the Theory of Computing (STOC’78). 216-226. https://doi.org/10.1145/800133.804350 10.1145/800133.804350 · Zbl 1282.68143 |
| [66] | Alexander Schrijver. 1986. Theory of linear and integer programming. John Wiley & Sons, Ltd., Chichester. isbn:0-471-90854-1 A Wiley-Interscience Publication · Zbl 0665.90063 |
| [67] | H. D. Sherali and W. P. Adams. 1990. A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems. SIAM J. Discret. Math., 3, 3 (1990), 411-430. https://doi.org/10.1137/0403036 10.1137/0403036 · Zbl 0712.90050 |
| [68] | Naum Z Shor. 1987. Class of global minimum bounds of polynomial functions. Cybernetics, 23, 6 (1987), 731-734. https://doi.org/10.1007/BF01070233 10.1007/BF01070233 · Zbl 0648.90058 |
| [69] | Madhur Tulsiani. 2009. CSP gaps and reductions in the Lasserre hierarchy. In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC’09). ACM, 303-312. https://doi.org/10.1145/1536414.1536457 10.1145/1536414.1536457 · Zbl 1304.90157 |
| [70] | Avi Wigderson. 1983. Improving the Performance Guarantee for Approximate Graph Coloring. J. ACM, 30, 4 (1983), 729-735. https://doi.org/10.1145/2157.2158 10.1145/2157.2158 · Zbl 0627.68057 |
| [71] | Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture. J. ACM, 67, 5 (2020), 30:1-30:78. https://doi.org/10.1145/3402029 arXiv:1704.01914. 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.
