{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T05:55:46Z","timestamp":1649138146643},"reference-count":92,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme","award":["\u00a0771005 ERC and \u00a0681988"]},{"name":"Austrian Science","award":["P29931 FWF"]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["18-20123S"]},{"name":"Charles University Research Centre program","award":["UNCE\/SCI\/022 and PRIMUS\/SCI\/12"]},{"name":"UK EPSRC","award":["EP\/R034516\/1"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,7,7]]},"abstract":"The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a\u00a0fixed constraint language on a\u00a0finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms\u2014high-dimensional symmetries of solution spaces\u2014to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases.<\/jats:p>\n \n The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a\u00a0new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a\u00a0fixed constraint language is equivalent to a\u00a0problem of this form. This allows us to identify a\u00a0\u201cmeasure of symmetry\u201d that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness\/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any\n k<\/jats:italic>\n \u2265 3, it is NP-hard to find a\u00a0(2\n k<\/jats:italic>\n -1)-colouring of a\u00a0given\n k<\/jats:italic>\n -colourable graph.\n <\/jats:p>","DOI":"10.1145\/3457606","type":"journal-article","created":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T16:23:56Z","timestamp":1626279836000},"page":"1-66","source":"Crossref","is-referenced-by-count":0,"title":["Algebraic Approach to Promise Constraint Satisfaction"],"prefix":"10.1145","volume":"68","author":[{"given":"Libor","family":"Barto","sequence":"first","affiliation":[{"name":"Charles University, Prague, Czechia"}]},{"given":"Jakub","family":"Bul\u00edn","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czechia"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-1245-3456","authenticated-orcid":false,"given":"Jakub","family":"Opr\u0161al","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"2816","DOI":"10.1016\/j.jpaa.2016.01.001","article-title":"Finitely generated equational classes","volume":"220","author":"Aichinger Erhard","year":"2016","journal-title":"J. Pure Appl. Algeb."},{"key":"e_1_2_1_2_1","first-page":"2","article-title":"The hardness of approximate optima in lattices, codes, and systems of linear equations","volume":"54","author":"Arora Sanjeev","year":"1997","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","article-title":"Proof verification and the hardness of approximation problems","volume":"45","author":"Arora Sanjeev","year":"1998","journal-title":"J. ACM"},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Probabilistic checking of proofs: A new characterization of NP","volume":"45","author":"Arora Sanjeev","year":"1998","journal-title":"J. ACM"},{"key":"e_1_2_1_5_1","volume-title":"Simplified inapproximability of hypergraph coloring via -agreeing families. (Apr","author":"Austrin Per","year":"2019"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Austrin Per","year":"2020"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"1554","DOI":"10.1137\/15M1006507","article-title":"-sat is NP-hard","volume":"46","author":"Austrin Per","year":"2017","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2462896.2462897","article-title":"On the usefulness of predicates","volume":"5","author":"Austrin Per","year":"2013","journal-title":"ACM Trans. Comput. Theor."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.4153\/CJM-2011-087-3","article-title":"Finitely related algebras in congruence distributive varieties have near unanimity terms","volume":"65","author":"Barto Libor","year":"2013","journal-title":"Canad. J. Math."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 34th ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201919)","author":"Barto Libor","year":"2019"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 32nd ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201917)","author":"Barto Libor","year":"2017"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem","volume":"8","author":"Barto Libor","year":"2012","journal-title":"Log. Meth. Comput. Sci."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2556646","article-title":"Constraint satisfaction problems solvable by local consistency methods","volume":"61","author":"Barto Libor","year":"2014","journal-title":"J. ACM"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1137\/130915479","article-title":"Robustly solvable constraint satisfaction problems","volume":"45","author":"Barto Libor","year":"2016","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_15_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Barto Libor","year":"2017"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"The wonderland of reflections","volume":"223","author":"Barto Libor","year":"2018","journal-title":"Israel J. Math."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1137\/18M1216213","article-title":"Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)","volume":"49","author":"Barto Libor","year":"2020","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0097539796302531","article-title":"Free bits, PCPs, and nonapproximability\u2014Towards tight results","volume":"27","author":"Bellare Mihir","year":"1998","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 20th ACM Symposium on Theory of Computing (STOC\u201988)","author":"Ben-Or Michael","year":"1988"},{"key":"e_1_2_1_20_1","volume-title":"Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G","author":"Bodirsky Manuel"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP\u201908)","author":"Bodirsky Manuel","year":"2008"},{"key":"e_1_2_1_22_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Bodirsky Manuel","year":"2017"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 34th ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201919)","author":"Bodirsky Manuel","year":"2019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01070906","article-title":"Galois theory for Post algebras","volume":"5","author":"Bodnarchuk V. G.","year":"1969","journal-title":"I. Cybernetics"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/BF01267873","article-title":"Galois theory for Post algebras","volume":"5","author":"Bodnarchuk V. G.","year":"1969","journal-title":"II. Cybernetics"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.)","volume":"50","author":"Brakensiek Joshua","year":"2016"},{"key":"e_1_2_1_27_1","volume-title":"Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy. ECCC Report No. 183","author":"Brakensiek Joshua","year":"2016"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization Conference: Algorithms and Techniques (APPROX\/RANDOM\u201917)","author":"Brakensiek Joshua","year":"2017"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Brakensiek Joshua","year":"2018"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Brakensiek Joshua","year":"2019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/20M1312745","article-title":"The power of the combined basic LP and affine relaxation for promise CSPs","volume":"49","author":"Brakensiek Joshua","year":"2020","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_32_1","volume-title":"Combinatorial Optimization Algorithms via Polymorphisms. (Jan","author":"Brown-Cohen Jonah","year":"2015"},{"key":"e_1_2_1_34_1","first-page":"3","article-title":"Classifying the complexity of constraints using finite algebras","volume":"34","author":"Bulatov Andrei","year":"2005","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_35_1","first-page":"5","article-title":"The complexity of the counting constraint satisfaction problem","volume":"60","author":"Bulatov Andrei A.","year":"2013","journal-title":"J. ACM"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the IEEE 58th Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Bulatov Andrei A.","year":"2017"},{"key":"e_1_2_1_37_1","volume-title":"Complexity of Constraints: An Overview of Current Research Themes","author":"Bulatov Andrei A."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 51st ACM SIGACT Symposium on the Theory of Computing (STOC\u201919)","author":"Bul\u00edn Jakub","year":"2019"},{"key":"e_1_2_1_39_1","first-page":"3","article-title":"Asking the metaquestions in constraint tractability","volume":"9","author":"Chen Hubie","year":"2017","journal-title":"ACM Trans. Comput. Theor."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the IEEE 57th Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Chen Hubie","year":"2016"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Dalmau V\u00edctor","year":"2017"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.jcss.2018.03.003","article-title":"Towards a characterization of constant-factor approximable finite-valued CSPs","volume":"97","author":"Dalmau Victor","year":"2018","journal-title":"J. Comput. System Sci."},{"key":"e_1_2_1_43_1","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"Dalmau V\u00edctor"},{"key":"e_1_2_1_44_1","first-page":"3","article-title":"The PCP theorem by gap amplification","volume":"54","author":"Dinur Irit","year":"2007","journal-title":"J. ACM"},{"key":"e_1_2_1_45_1","first-page":"5","article-title":"A new multilayered PCP and the hardness of hypergraph vertex cover","volume":"34","author":"Dinur Irit","year":"2005","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1137\/07068062X","article-title":"Conditional hardness for approximate coloring","volume":"39","author":"Dinur Irit","year":"2009","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_47_1","first-page":"5","article-title":"The hardness of 3-uniform hypergraph coloring","volume":"25","author":"Dinur Irit","year":"2005","journal-title":"Combinatorica"},{"key":"e_1_2_1_48_1","first-page":"1","article-title":"The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory","volume":"28","author":"Feder Tom\u00e1s","year":"1998","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Ficak Miron"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321921.321926","article-title":"The complexity of near-optimal graph coloring","volume":"23","author":"Garey M. R.","year":"1976","journal-title":"J. ACM"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","article-title":"Closed systems of functions and predicates","volume":"27","author":"Geiger David","year":"1968","journal-title":"Pacific J. Math."},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1137\/140995520","article-title":"Super-polylogarithmic hypergraph coloring hardness via low-degree long codes","volume":"46","author":"Guruswami Venkatesan","year":"2017","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/S0895480100376794","article-title":"On the hardness of 4-coloring a 3-colorable graph","volume":"18","author":"Guruswami Venkatesan","year":"2004","journal-title":"SIAM J. Disc. Math."},{"key":"e_1_2_1_54_1","volume-title":"Strong inapproximability results on balanced rainbow-colorable hypergraphs. Combinatorica (14","author":"Guruswami Venkatesan","year":"2017"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Guruswami Venkatesan"},{"key":"e_1_2_1_56_1","first-page":"4","article-title":"Some optimal inapproximability results","volume":"48","author":"H\u00e5stad Johan","year":"2001","journal-title":"J. ACM"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","article-title":"On the complexity of -coloring","volume":"48","author":"Hell Pavol","year":"1990","journal-title":"J. Combin. Theor. Ser. B"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press. Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_59_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX","author":"Huang Sangxia","year":"2013"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","first-page":"3023","DOI":"10.1137\/090775646","article-title":"Tractability and learnability arising from algebras with few subpowers","volume":"39","author":"Idziak Pawe\u0142 M.","year":"2010","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_61_1","first-page":"1","article-title":"On the algebraic structure of combinatorial problems","volume":"200","author":"Jeavons Peter","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"e_1_2_1_62_1","first-page":"4","article-title":"Closure properties of constraints","volume":"44","author":"Jeavons Peter","year":"1997","journal-title":"J. ACM"},{"key":"e_1_2_1_63_1","article-title":"Coloring 3-colorable graphs with less than colors","volume":"64","author":"Mikkel Thorup Kawarabayashi","year":"2017","journal-title":"J. ACM"},{"key":"e_1_2_1_64_1","volume-title":"On the hardness of approximating the chromatic number. Combinatorica 20, 3 (01","author":"Khanna Sanjeev","year":"2000"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 600\u2013609","author":"Khot Subhash","year":"2001"},{"key":"e_1_2_1_66_1","volume-title":"Vardi","author":"Kolaitis Phokion G.","year":"2008"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1137\/16M1091836","article-title":"The complexity of general-valued CSPs","volume":"46","author":"Kolmogorov Vladimir","year":"2017","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the IEEE 60th Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Krokhin Andrei","year":"2019"},{"key":"e_1_2_1_69_1","volume-title":"Topology and adjunction in promise constraint satisfaction. (Mar","author":"Krokhin Andrei","year":"2020"},{"key":"e_1_2_1_70_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Krokhin Andrei","year":"2017"},{"key":"e_1_2_1_71_1","volume-title":"Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS\u201912)","author":"Kun G\u00e1bor","year":"2012"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1016\/j.ejc.2015.07.011","article-title":"A new line of attack on the dichotomy conjecture","volume":"52","author":"Kun G\u00e1bor","year":"2016","journal-title":"Eur. J. Comb."},{"key":"e_1_2_1_73_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Larose Benoit","year":"2017"},{"key":"e_1_2_1_74_1","volume-title":"Bounded width problems and algebras. Algeb. Univers. 56, 3 (01","author":"Larose Benoit","year":"2007"},{"key":"e_1_2_1_75_1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","article-title":"Kneser\u2019s conjecture, chromatic number, and homotopy","volume":"25","author":"Lov\u00e1sz L\u00e1szlo","year":"1978","journal-title":"J. Combin. Theor. Ser. A"},{"key":"e_1_2_1_76_1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1017\/S0963548300000730","article-title":"A random recolouring method for graphs and hypergrams","volume":"2","author":"McDiarmid Colin","year":"1993","journal-title":"Combinat. Proba. Comput."},{"key":"e_1_2_1_77_1","article-title":"On Malcev conditions","volume":"17","author":"Neumann Walter D.","year":"1974","journal-title":"J. Austral. Math. Soc."},{"key":"e_1_2_1_78_1","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1112\/blms.12097","article-title":"The weakest nontrivial idempotent equations","volume":"49","author":"Ol\u0161\u00e1k Miroslav","year":"2017","journal-title":"Bull. London Math. Soc."},{"key":"e_1_2_1_79_1","unstructured":"Miroslav Ol\u0161\u00e1k. 2018. Personal communication. Miroslav Ol\u0161\u00e1k. 2018. Personal communication."},{"key":"e_1_2_1_80_1","first-page":"1","article-title":"Loop conditions","volume":"81","author":"Ol\u0161\u00e1k Miroslav","year":"2019","journal-title":"Algeb. Univers."},{"key":"e_1_2_1_81_1","volume-title":"Taylor\u2019s modularity conjecture and related problems for idempotent varieties. Order (Nov","author":"Opr\u0161al Jakub","year":"2017"},{"key":"e_1_2_1_82_1","unstructured":"Michael Pinsker. 2015. Algebraic and model theoretic methods in constraint satisfaction. (2015). arXiv:1507.00931. Michael Pinsker. 2015. Algebraic and model theoretic methods in constraint satisfaction. (2015). arXiv:1507.00931."},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/S0012-365X(01)00297-7","article-title":"Galois theory for minors of finite functions","volume":"254","author":"Pippenger Nicholas","year":"2002","journal-title":"Disc. Math."},{"key":"e_1_2_1_84_1","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","article-title":"A parallel repetition theorem","volume":"27","author":"Raz Ran","year":"1998","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_85_1","first-page":"4","article-title":"Undirected connectivity in log-space","volume":"55","author":"Reingold Omer","year":"2008","journal-title":"J. ACM"},{"key":"e_1_2_1_86_1","volume-title":"Proceedings of the 10th ACM Symposium on Theory of Computing (STOC\u201978)","author":"Schaefer Thomas J.","year":"1978"},{"key":"e_1_2_1_87_1","volume-title":"Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26, 3","author":"Schrijver Alexander","year":"1978"},{"key":"e_1_2_1_88_1","first-page":"1","article-title":"A strong Mal\u2019cev condition for locally finite varieties omitting the unary type","volume":"64","author":"Siggers Mark H.","year":"2010","journal-title":"Algeb. Univers."},{"key":"e_1_2_1_89_1","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02945141","article-title":"Characterizing Mal\u2019cev conditions","volume":"3","author":"Taylor Walter","year":"1973","journal-title":"Algeb. Univers."},{"key":"e_1_2_1_90_1","article-title":"The complexity of finite-valued CSPs","volume":"63","author":"Thapper Johan","year":"2016","journal-title":"J. ACM"},{"key":"e_1_2_1_91_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Wrochna Marcin","year":"2020"},{"key":"e_1_2_1_92_1","volume-title":"Proceedings of the IEEE 58th Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Zhuk Dmitriy","year":"2017"},{"key":"e_1_2_1_93_1","first-page":"5","article-title":"A proof of the CSP dichotomy conjecture","volume":"67","author":"Zhuk Dmitriy","year":"2020","journal-title":"J. ACM"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T16:27:03Z","timestamp":1626280023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,7]]},"references-count":92,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7,7]]}},"alternative-id":["10.1145\/3457606"],"URL":"http:\/\/dx.doi.org\/10.1145\/3457606","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2021,7,7]]}}}