{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:41:43Z","timestamp":1774946503962,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Grantov\u00e1 Agentura \u00f0esk\u00e9 Republiky","award":["18-20123S"],"award-info":[{"award-number":["18-20123S"]}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["681988"],"award-info":[{"award-number":["681988"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R034516\/1"],"award-info":[{"award-number":["EP\/R034516\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007397","name":"Univerzita Karlova v Praze","doi-asserted-by":"publisher","award":["UNCE\/SCI\/022, PRIMUS\/SCI\/12"],"award-info":[{"award-number":["UNCE\/SCI\/022, PRIMUS\/SCI\/12"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P29931"],"award-info":[{"award-number":["P29931"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316300","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"602-613","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Algebraic approach to promise constraint satisfaction"],"prefix":"10.1145","author":[{"given":"Jakub","family":"Bul\u00edn","sequence":"first","affiliation":[{"name":"Charles University in Prague, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[{"name":"University of Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Opr\u0161al","sequence":"additional","affiliation":[{"name":"University of Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_3_2_1_2_1","volume-title":"Improved Inapproximability of Rainbow Coloring. ArXiv e-prints (Oct","author":"Austrin Per","year":"2018","unstructured":"Per Austrin , Amey Bhangale , and Aditya Potukuchi . 2018. Improved Inapproximability of Rainbow Coloring. ArXiv e-prints (Oct . 2018 ). arXiv: 1810.02784 Per Austrin, Amey Bhangale, and Aditya Potukuchi. 2018. Improved Inapproximability of Rainbow Coloring. ArXiv e-prints (Oct. 2018). arXiv: 1810.02784"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Libor Barto. 2019. Promises make finite (constraint satisfaction) problems infinitary. (2019).  Libor Barto. 2019. Promises make finite (constraint satisfaction) problems infinitary. (2019).","DOI":"10.1109\/LICS.2019.8785671"},{"key":"e_1_3_2_1_5_1","volume-title":"LICS","year":"2019","unstructured":"to appear in LICS 2019 . to appear in LICS 2019."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_3_2_1_8_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Andrei Krokhin , and Ross Willard . 2017 . Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.) . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1\u201344. Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1\u201344."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_2_1_10_1","unstructured":"Mihir Bellare Oded Goldreich and Madhu Sudan. 1998.  Mihir Bellare Oded Goldreich and Madhu Sudan. 1998."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_3_2_1_13_1","volume-title":"Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G","author":"Bodirsky Manuel","unstructured":"Manuel Bodirsky . 2008. Constraint Satisfaction Problems with Infinite Templates . In Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G . Kolaitis, and Heribert Vollmer (Eds.), Vol. 5250 . Manuel Bodirsky. 2008. Constraint Satisfaction Problems with Infinite Templates. In Complexity of Constraints (2009-05-05) (Lecture Notes in Computer Science), Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer (Eds.), Vol. 5250."},{"key":"e_1_3_2_1_14_1","unstructured":"Springer 196\u2013228.  Springer 196\u2013228."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_16"},{"key":"e_1_3_2_1_16_1","unstructured":"Joshua Brakensiek and Venkatesan Guruswami. 2016.  Joshua Brakensiek and Venkatesan Guruswami. 2016."},{"key":"e_1_3_2_1_17_1","volume-title":"Hardness Results for Graph and Hypergraph Colorings. In 31st Conference on Computational Complexity (CCC 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.)","volume":"50","author":"New","unstructured":"New Hardness Results for Graph and Hypergraph Colorings. In 31st Conference on Computational Complexity (CCC 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.) , Vol. 50 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 14:1\u201314:27. New Hardness Results for Graph and Hypergraph Colorings. In 31st Conference on Computational Complexity (CCC 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.), Vol. 50. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 14:1\u201314:27."},{"key":"e_1_3_2_1_18_1","unstructured":"Joshua Brakensiek and Venkatesan Guruswami. 2017.  Joshua Brakensiek and Venkatesan Guruswami. 2017."},{"key":"e_1_3_2_1_19_1","volume-title":"APPROX\/RANDOM 2017","author":"Strong Inapproximability The Quest","year":"2017","unstructured":"The Quest for Strong Inapproximability Results with Perfect Completeness . In Approximation , Randomization, and Combinatorial Optimization . Algorithms and Techniques , APPROX\/RANDOM 2017 , August 16-18, 2017 , Berkeley, CA, USA. 4:1\u20134:20. The Quest for Strong Inapproximability Results with Perfect Completeness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA. 4:1\u20134:20."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.117"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.28"},{"key":"e_1_3_2_1_22_1","volume-title":"Combinatorial Optimization Algorithms via Polymorphisms. CoRR abs\/1501.01598","author":"Brown-Cohen Jonah","year":"2015","unstructured":"Jonah Brown-Cohen and Prasad Raghavendra . 2015. Combinatorial Optimization Algorithms via Polymorphisms. CoRR abs\/1501.01598 ( 2015 ). Jonah Brown-Cohen and Prasad Raghavendra. 2015. Combinatorial Optimization Algorithms via Polymorphisms. CoRR abs\/1501.01598 (2015)."},{"key":"e_1_3_2_1_23_1","unstructured":"Andrei Bulatov and Peter Jeavons. 2001.  Andrei Bulatov and Peter Jeavons. 2001."},{"key":"e_1_3_2_1_24_1","unstructured":"Algebraic structures in combinatorial problems. Technical Report.  Algebraic structures in combinatorial problems. Technical Report."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_28_1","unstructured":"Jakub Bul\u00edn Andrei Krokhin and Jakub Opr\u0161al. 2018.  Jakub Bul\u00edn Andrei Krokhin and Jakub Opr\u0161al. 2018."},{"key":"e_1_3_2_1_29_1","volume-title":"ArXiv e-prints","author":"Algebraic","year":"2018","unstructured":"Algebraic approach to promise constraint satisfaction. ArXiv e-prints ( 2018 ). arXiv: 1811.00970 Algebraic approach to promise constraint satisfaction. ArXiv e-prints (2018). arXiv: 1811.00970"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134757"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.63"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039708"},{"key":"e_1_3_2_1_33_1","unstructured":"Victor Dalmau Andrei Krokhin and Rajsekar Manokaran. 2018.  Victor Dalmau Andrei Krokhin and Rajsekar Manokaran. 2018."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. System Sci. 97 14\u201327.  Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. System Sci. 97 14\u201327.","DOI":"10.1016\/j.jcss.2018.03.003"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_3_2_1_39_1","unstructured":"Venkatesan Guruswami and Sanjeev Khanna. 2004.  Venkatesan Guruswami and Sanjeev Khanna. 2004."},{"key":"e_1_3_2_1_40_1","volume-title":"SIAM Journal on Discrete Mathematics 18, 1","author":"Colorable Graph On","year":"2004","unstructured":"On the Hardness of 4-Coloring a 3- Colorable Graph . SIAM Journal on Discrete Mathematics 18, 1 ( 2004 ), 30\u201340. On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM Journal on Discrete Mathematics 18, 1 (2004), 30\u201340."},{"key":"e_1_3_2_1_41_1","unstructured":"Venkatesan Guruswami and Euiwoong Lee. 2017.  Venkatesan Guruswami and Euiwoong Lee. 2017."},{"key":"e_1_3_2_1_42_1","unstructured":"Strong inapproximability results on balanced rainbow-colorable hypergraphs. Combinatorica (14 Dec 2017).  Strong inapproximability results on balanced rainbow-colorable hypergraphs. Combinatorica (14 Dec 2017)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_44_1","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 1990.  Pavol Hell and Jaroslav Ne\u0161et\u0159il. 1990."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_2_1_46_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX","author":"Huang Sangxia","year":"2013","unstructured":"Sangxia Huang . 2013. Improved Hardness of Approximating Chromatic Number . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013 , and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.). Springer , Berlin, Heidelberg, 233\u2013243. Sangxia Huang. 2013. Improved Hardness of Approximating Chromatic Number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.). Springer, Berlin, Heidelberg, 233\u2013243."},{"key":"e_1_3_2_1_47_1","unstructured":"Pawe\u0142 M. Idziak Petar Markovi\u0107 Ralph McKenzie Matthew Valeriote and Ross Willard. 2010.  Pawe\u0142 M. Idziak Petar Markovi\u0107 Ralph McKenzie Matthew Valeriote and Ross Willard. 2010."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_3_2_1_49_1","unstructured":"Peter Jeavons David Cohen and Marc Gyssens. 1997.  Peter Jeavons David Cohen and Marc Gyssens. 1997."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3001582"},{"key":"e_1_3_2_1_52_1","unstructured":"Sanjeev Khanna Nathan Linial and Shmuel Safra. 2000.  Sanjeev Khanna Nathan Linial and Shmuel Safra. 2000."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"On the Hardness of Approximating the Chromatic Number. Combinatorica 20 3 (01 Mar 2000) 393\u2013 415.  On the Hardness of Approximating the Chromatic Number. Combinatorica 20 3 (01 Mar 2000) 393\u2013 415.","DOI":"10.1007\/s004930070013"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875607"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_3_2_1_56_1","unstructured":"Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). 2017.  Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). 2017."},{"key":"e_1_3_2_1_57_1","volume-title":"Complexity and Approximability. Dagstuhl Follow-Ups","author":"Satisfaction Problem The Constraint","unstructured":"The Constraint Satisfaction Problem : Complexity and Approximability. Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik . The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_58_1","volume-title":"Probability &amp","author":"McDiarmid Colin","year":"1993","unstructured":"Colin McDiarmid . 1993. A Random Recolouring Method for Graphs and Hypergrams. Combinatorics , Probability &amp ; Computing 2 ( 1993 ), 363\u2013365. Colin McDiarmid. 1993. A Random Recolouring Method for Graphs and Hypergrams. Combinatorics, Probability & Computing 2 (1993), 363\u2013365."},{"key":"e_1_3_2_1_59_1","unstructured":"Michael Pinsker. 2015.  Michael Pinsker. 2015."},{"key":"e_1_3_2_1_60_1","volume-title":"ArXiv e-prints","author":"Algebraic","year":"2015","unstructured":"Algebraic and model theoretic methods in constraint satisfaction. ArXiv e-prints ( 2015 ). arXiv: 1507.00931 Algebraic and model theoretic methods in constraint satisfaction. ArXiv e-prints (2015). arXiv: 1507.00931"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2974019"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316300","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:00Z","timestamp":1750204440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":63,"alternative-id":["10.1145\/3313276.3316300","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316300","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}