{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:07Z","timestamp":1750309567754,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T00:00:00Z","timestamp":1745366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"EPSRC Fellowship","award":["EP\/X033201\/1"],"award-info":[{"award-number":["EP\/X033201\/1"]}]},{"DOI":"10.13039\/100014013","name":"UKRI","doi-asserted-by":"crossref","award":["EP\/X024431\/1"],"award-info":[{"award-number":["EP\/X024431\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Centre, Poland under the Weave-UNISONO call in the Weave programme","award":["2021\/03\/Y\/ST6\/00171"],"award-info":[{"award-number":["2021\/03\/Y\/ST6\/00171"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>\n            The 1\n            <jats:sc>-in-<\/jats:sc>\n            3 and N\n            <jats:sc>ot<\/jats:sc>\n            -A\n            <jats:sc>ll<\/jats:sc>\n            -E\n            <jats:sc>qual<\/jats:sc>\n            satisfiability problems for Boolean CNF formulas are two well-known\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -hard problems. In contrast, the\n            <jats:italic>promise<\/jats:italic>\n            1\n            <jats:sc>-in-<\/jats:sc>\n            3\n            <jats:sc>vs<\/jats:sc>\n            . N\n            <jats:sc>ot<\/jats:sc>\n            -A\n            <jats:sc>ll<\/jats:sc>\n            -E\n            <jats:sc>qual<\/jats:sc>\n            problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a\n            <jats:italic>rainbow-free<\/jats:italic>\n            structure and establish a complexity dichotomy for the resulting class of computational problems.\n          <\/jats:p>","DOI":"10.1145\/3719007","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T15:04:01Z","timestamp":1740063841000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["1\n            <scp>-in-<\/scp>\n            3\n            <scp>vs<\/scp>\n            . N\n            <scp>ot<\/scp>\n            -A\n            <scp>ll<\/scp>\n            -E\n            <scp>qual<\/scp>\n            : Dichotomy of a Broken Promise"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9491-2016","authenticated-orcid":false,"given":"Lorenzo","family":"Ciardo","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom of Great Britain and Northern Ireland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1839-4824","authenticated-orcid":false,"given":"Marcin","family":"Kozik","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Krakow, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4373-8227","authenticated-orcid":false,"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[{"name":"Durham University, Durham, United Kingdom of Great Britain and Northern Ireland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3684-9412","authenticated-orcid":false,"given":"Tamio-Vesa","family":"Nakajima","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom of Great Britain and Northern Ireland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom of Great Britain and Northern Ireland"}]}],"member":"320","published-online":{"date-parts":[[2025,4,23]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1137\/1.9781611977073.48","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922)","author":"Atserias Albert","year":"2022","unstructured":"Albert Atserias and V\u00edctor Dalmau. 2022. Promise constraint satisfaction and width. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922), 1129\u20131153. DOI: 10.1137\/1.9781611977073.48"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_3_3_4_2","series-title":"LIPIcs","first-page":"10:1","volume-title":"Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS \u201921)","volume":"187","author":"Barto Libor","year":"2021","unstructured":"Libor Barto, Diego Battistelli, and Kevin M. Berg. 2021. Symmetric promise constraint satisfaction problems: Beyond the Boolean case. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS \u201921), LIPIcs, Vol. 187, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 10:1\u201310:16. DOI: 10.4230\/LIPIcs.STACS.2021"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1137\/1.9781611977073.50","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922)","author":"Barto Libor","year":"2022","unstructured":"Libor Barto and Marcin Kozik. 2022. Combinatorial gap theorem and reductions between promise CSPs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922), 1204\u20131220. DOI: 10.1137\/1.9781611977073.50"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","unstructured":"Libor Barto Andrei Krokhin and Ross Willard. 2017. Polymorphisms and how to use them Dagstuhl Follow-Ups Vol. 7 Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik Dagstuhl Germany 1\u201344. DOI: 10.4230\/DFU.Vol7.15301.1","DOI":"10.4230\/DFU.Vol7.15301.1"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_3_10_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/978-3-540-70583-3_16","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP \u201908)","volume":"5126","author":"Bodirsky Manuel","year":"2008","unstructured":"Manuel Bodirsky and Martin Grohe. 2008. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP \u201908), Lecture Notes in Computer Science, Vol. 5126, Springer, 184\u2013196. DOI: 10.1007\/978-3-540-70583-3_16"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2019.23"},{"key":"e_1_3_3_12_2","series-title":"LIPIcs","first-page":"14:1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u201916)","volume":"50","author":"Brakensiek Joshua","year":"2016","unstructured":"Joshua Brakensiek and Venkatesan Guruswami. 2016. New hardness results for graph and hypergraph colorings. In Proceedings of the 31st Conference on Computational Complexity (CCC\u201916), LIPIcs, Vol. 50, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 14:1\u201314:27. DOI: 10.4230\/LIPIcs.CCC.2016.14"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M128212X"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","unstructured":"Joshua Brakensiek Venkatesan Guruswami and Sai Sandeep. 2023. Conditional dichotomy of Boolean ordered promise CSPs. TheoretiCS 2. Retrieved from https:\/\/theoretics.episciences.org\/10447","DOI":"10.46298\/theoretics.23.2"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1145\/3564246.3585180","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC\u201923)","author":"Brakensiek Joshua","year":"2023","unstructured":"Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. 2023. SDPs and robust satisfiability of promise CSP. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC\u201923). ACM, 609\u2013622. DOI: 10.1145\/3564246.3585180"},{"key":"e_1_3_3_16_2","unstructured":"Alex Brandts. 2022. Promise Constraint Satisfaction Problems. Ph.D. Dissertation. University of Oxford. Retrieved from https:\/\/ora.ouls.ox.ac.uk\/objects\/uuid:5efeff56-d5c8-42e8-9bd2-95243a1367ad"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3470867"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2022.104954"},{"key":"e_1_3_3_19_2","first-page":"228","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201921)","author":"Braverman Mark","year":"2021","unstructured":"Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer. 2021. An invariance principle for the multi-slice, with applications. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201921). IEEE, 228\u2013236. DOI: 10.1109\/FOCS52979.2021.00030"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1109\/FOCS.2017.37","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201917)","author":"Bulatov Andrei","year":"2017","unstructured":"Andrei Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201917), 319\u2013330. DOI: 10.1109\/FOCS.2017.37"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1592451.1592453"},{"key":"e_1_3_3_23_2","first-page":"24:1","volume-title":"Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201924)","author":"Ciardo Lorenzo","year":"2024","unstructured":"Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, and Stanislav \u017divn\u00fd. 2024. 1-in-3 vs. not-all-equal: Dichotomy of a broken promise. In Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201924). ACM, 24:1\u201324:12. DOI: 10.1145\/3661814.3662069"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"2256","DOI":"10.1137\/1.9781611977554.ch86","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201923)","author":"Ciardo Lorenzo","year":"2023","unstructured":"Lorenzo Ciardo and Stanislav \u017divn\u00fd. 2023. Approximate graph colouring and crystals. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201923), 2256\u20132267. DOI: 10.1137\/1.9781611977554.ch86"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/3564246.3585112","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC \u201923)","author":"Ciardo Lorenzo","year":"2023","unstructured":"Lorenzo Ciardo and Stanislav \u017divn\u00fd. 2023. Approximate graph colouring and the hollow shadow. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC \u201923). ACM, 623\u2013631. DOI: 10.1145\/3564246.3585112"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/22M1476435"},{"key":"e_1_3_3_27_2","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC \u201971)","author":"Cook Stephen A.","year":"1971","unstructured":"Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC \u201971). ACM, 151\u2013158. DOI: 10.1145\/800157.805047"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_3_31_2","series-title":"LIPIcs","first-page":"57:1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919)","volume":"132","author":"Ficak Miron","year":"2019","unstructured":"Miron Ficak, Marcin Kozik, Miroslav Ol\u0161\u00e1k, and Szymon Stankiewicz. 2019. Dichotomy for symmetric Boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919), LIPIcs, Vol. 132, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 57:1\u201357:12. DOI: 10.4230\/LIPIcs.ICALP.2019.57"},{"key":"e_1_3_3_32_2","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"34:1","volume-title":"Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS \u201924)","volume":"289","author":"Filakovsk\u00fd Marek","year":"2024","unstructured":"Marek Filakovsk\u00fd, Tamio-Vesa Nakajima, Jakub Opr\u0161al, Gianluca Tasinato, and Uli Wagner. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS \u201924). Olaf Beyersdorff, Mamadou Moustapha Kant\u00e9, Orna Kupferman, and Daniel Lokshtanov (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 289, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 34:1\u201334:19. DOI: 10.4230\/LIPIcs.STACS.2024.34"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_3_3_34_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman."},{"key":"e_1_3_3_35_2","series-title":"LIPIcs","first-page":"62:1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP \u201921)","volume":"198","author":"Guruswami Venkatesan","year":"2020","unstructured":"Venkatesan Guruswami and Sai Sandeep. 2020. d-To-1 hardness of coloring 3-colorable graphs with O(1) colors. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP \u201921), LIPIcs, Vol. 198, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 62:1\u201362:12. DOI: 10.4230\/LIPIcs.ICALP.2020.62"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122553"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.2307\/2315334"},{"key":"e_1_3_3_38_2","series-title":"LIPIcs","first-page":"51:1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM \u201923)","volume":"275","author":"Hecht Yahli","year":"2023","unstructured":"Yahli Hecht, Dor Minzer, and Muli Safra. 2023. NP-hardness of almost coloring almost 3-colorable graphs. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM \u201923). Nicole Megow and Adam D. Smith (Eds.), LIPIcs, Vol. 275, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 51:1\u201351:12. DOI: 10.4230\/LIPICS.APPROX\/RANDOM.2023.51"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_3_40_2","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"Hell Pavol","year":"2004","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press."},{"key":"e_1_3_3_41_2","first-page":"233","volume-title":"Proceedings of the 16th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques and the 17th International Workshop on Randomization and Computation (APPROX-RANDOM \u201913)","author":"Huang Sangxia","year":"2013","unstructured":"Sangxia Huang. 2013. Improved hardness of approximating chromatic number. In Proceedings of the 16th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques and the 17th International Workshop on Randomization and Computation (APPROX-RANDOM \u201913). Springer, 233\u2013243. DOI: 10.1007\/978-3-642-40328-6_17"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208040"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proceedings of the Complexity of Computer Computations","author":"Karp Richard M.","year":"1972","unstructured":"Richard M. Karp. 1972. Reducibility among combinatorial problems. In Proceedings of the Complexity of Computer Computations, 85\u2013103. DOI: 10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1378223"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2008.12.048"},{"key":"e_1_3_3_49_2","unstructured":"Tamio-Vesa Nakajima Zephyr Verwimp Marcin Wrochna and Stanislav \u017divn\u00fd. 2025. Complexity of approximate conflict-free linearly-ordered and nonmonochromatic hypergraph colourings. arXiv:2501.12062. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2501.12062"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3570909"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3673655"},{"key":"e_1_3_3_52_2","first-page":"216","volume-title":"Proceedings of the 10th Annual ACM Symposium on the Theory of Computing (STOC \u201978)","author":"Schaefer Thomas","year":"1978","unstructured":"Thomas Schaefer. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on the Theory of Computing (STOC \u201978), 216\u2013226. DOI: 10.1145\/800133.804350"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079245"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90262-9"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3719007","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3719007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:08Z","timestamp":1750295948000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3719007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,23]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3719007"],"URL":"https:\/\/doi.org\/10.1145\/3719007","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2025,4,23]]},"assertion":[{"value":"2024-09-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}