{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:47Z","timestamp":1772313227227,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/J000078\/1"],"award-info":[{"award-number":["EP\/J000078\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["TIN2010-20967-C04-02"],"award-info":[{"award-number":["TIN2010-20967-C04-02"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 \u2212\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>\u03b5<\/jats:italic>\n            ))-fraction of constraints for each (1 \u2212\n            <jats:italic>\u03b5<\/jats:italic>\n            )-satisfiable instance (i.e., such that at most a\n            <jats:italic>\u03b5<\/jats:italic>\n            -fraction of constraints needs to be removed to make the instance satisfiable), where\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>\u03b5<\/jats:italic>\n            ) \u2192 0 as\n            <jats:italic>\u03b5<\/jats:italic>\n            \u2192 0. We establish an algebraic framework for analyzing constraint satisfaction problems admitting an efficient robust algorithm with functions\n            <jats:italic>f<\/jats:italic>\n            of a given growth rate. We use this framework to derive hardness results. We also describe three classes of problems admitting an efficient robust algorithm such that\n            <jats:italic>f<\/jats:italic>\n            is\n            <jats:italic>O<\/jats:italic>\n            (1\/log (1\/\n            <jats:italic>\u03b5<\/jats:italic>\n            )),\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03b5<\/jats:italic>\n            <jats:sup>1\/k<\/jats:sup>\n            ) for some\n            <jats:italic>k<\/jats:italic>\n            &gt; 1, and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03b5<\/jats:italic>\n            ), respectively. Finally, we give a complete classification of robust satisfiability with a given\n            <jats:italic>f<\/jats:italic>\n            for the Boolean case.\n          <\/jats:p>","DOI":"10.1145\/2540090","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Robust Satisfiability for CSPs"],"prefix":"10.1145","volume":"5","author":[{"given":"V\u00edctor","family":"Dalmau","sequence":"first","affiliation":[{"name":"University Pompeu Fabra"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[{"name":"Durham University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214061"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.24"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Galois theory for post algebras, i","volume":"3","author":"Bodnarchuk V. G.","year":"1969","unstructured":"Bodnarchuk , V. G. , Kaluzhnin , L. A. , Kotov , V. N. , and Romov , B. A. 1969 . Galois theory for post algebras, i . Kibernetika 3 , 1 -- 10 . Bodnarchuk, V. G., Kaluzhnin, L. A., Kotov, V. N., and Romov, B. A. 1969. Galois theory for post algebras, i. Kibernetika 3, 1--10.","journal-title":"Kibernetika"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_8_1","unstructured":"Bulatov A. 2009. Bounded relational width. http:\/\/www.cs.sfu.ca\/~abulatov\/papers\/relwidth.pdf.  Bulatov A. 2009. Bounded relational width. http:\/\/www.cs.sfu.ca\/~abulatov\/papers\/relwidth.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Burris S. and Sankappanavar H. P. 1981. A Course in Universal Algebra Graduate Text in Mathematics. Springer. http:\/\/www.math.uwaterloo.ca\/~snburris\/htdocs\/ualg.html.  Burris S. and Sankappanavar H. P. 1981. A Course in Universal Algebra Graduate Text in Mathematics . Springer. http:\/\/www.math.uwaterloo.ca\/~snburris\/htdocs\/ualg.html.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exq030"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541893"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Cohen D. and Jeavons P. 2006. The complexity of constraint languages. In Handbook of Constraint Programming F. Rossi P. van Beek and T. Walsh Eds. Elsevier Chapter 8.  Cohen D. and Jeavons P. 2006. The complexity of constraint languages. In Handbook of Constraint Programming F. Rossi P. van Beek and T. Walsh Eds. Elsevier Chapter 8.","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Complexity classifications of boolean constraint satisfaction problems","volume":"7","author":"Creignou N.","year":"2001","unstructured":"Creignou , N. , Khanna , S. , and Sudan , M. 2001 . Complexity classifications of boolean constraint satisfaction problems . ACM Trans. SIAM Monographs Disc. Math. Appl. 7 , 1 -- 24 . Creignou, N., Khanna, S., and Sudan, M. 2001. Complexity classifications of boolean constraint satisfaction problems. ACM Trans. SIAM Monographs Disc. Math. Appl. 7, 1--24.","journal-title":"ACM Trans. SIAM Monographs Disc. Math. Appl."},{"key":"e_1_2_1_20_1","volume-title":"Eds","author":"Creignou N.","year":"2008","unstructured":"Creignou , N. , Kolaitis , P. G. , and Vollmer , H. , Eds . 2008 . Complexity of Constraints. Lecture Notes in Computer Science, vol. 5250 , Springer . Creignou, N., Kolaitis, P. G., and Vollmer, H., Eds. 2008. Complexity of Constraints. Lecture Notes in Computer Science, vol. 5250, Springer."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.020"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/647486.726506"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391290"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_2"},{"key":"e_1_2_1_29_1","volume-title":"General Lattice Theory","author":"Gratzer G.","unstructured":"Gratzer , G. 2002. General Lattice Theory . Birkhauser . Gratzer, G. 2002. General Lattice Theory. Birkhauser."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Conference on Innovations in Computer Science (ICS\u201911)","author":"Guruswami V.","unstructured":"Guruswami , V. , Makarychev , Y. , Raghavendra , P. , Steurer , D. , and Zhou , Y . 2011. Finding almost perfect graph bisections . In Proceedings of the Conference on Innovations in Computer Science (ICS\u201911) . 321--337. Guruswami, V., Makarychev, Y., Raghavendra, P., Steurer, D., and Zhou, Y. 2011. Finding almost perfect graph bisections. In Proceedings of the Conference on Innovations in Computer Science (ICS\u201911). 321--337."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a011"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0256-y"},{"key":"e_1_2_1_34_1","volume-title":"The Structure of Finite Algebras","author":"Hobby D.","unstructured":"Hobby , D. and McKenzie , R. 1988. The Structure of Finite Algebras . American Mathematical Society . Hobby, D. and McKenzie, R. 1988. The Structure of Finite Algebras. American Mathematical Society."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444644X"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911)","author":"Jonsson P.","unstructured":"Jonsson , P. , Kuivinen , F. , and Thapper , J . 2011. Min CSP on four elements: Moving beyond submodularity . In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911) . 438--453. Jonsson, P., Kuivinen, F., and Thapper, J. 2011. Min CSP on four elements: Moving beyond submodularity. In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911). 438--453."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.19"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_41_1","unstructured":"Kozik M. Krokhin A. Valeriote M. and Willard R. 2013. Characterizations of several maltsev conditions. http:\/\/www.math.uwaterloo.ca\/~rdwillar\/documents\/Publications\/MaltsevPaper.pdf.  Kozik M. Krokhin A. Valeriote M. and Willard R. 2013. Characterizations of several maltsev conditions. http:\/\/www.math.uwaterloo.ca\/~rdwillar\/documents\/Publications\/MaltsevPaper.pdf."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.048"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.007"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806790"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1970"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_49_1","volume-title":"Seminaire de Mathematiques Superieures","author":"Szendrei A.","unstructured":"Szendrei , A. 1986. Clones in Universal Algebra . In Seminaire de Mathematiques Superieures , vol. 99 , Les Presses de l\u2019 Universite de Montreal. Szendrei, A. 1986. Clones in Universal Algebra. In Seminaire de Mathematiques Superieures, vol. 99, Les Presses del\u2019 Universite de Montreal."},{"key":"e_1_2_1_50_1","volume-title":"Research and Exposition in Mathematics, Heldermann, 209--239","author":"Szendrei A.","year":"1992","unstructured":"Szendrei , A. 1992 . A survey on strictly simple algebras and minimal varieties . In Research and Exposition in Mathematics, Heldermann, 209--239 . Szendrei, A. 1992. A survey on strictly simple algebras and minimal varieties. In Research and Exposition in Mathematics, Heldermann, 209--239."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-2009-023-2"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276869"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2540090","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2540090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:33Z","timestamp":1750234233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2540090"}},"subtitle":["Hardness and Algorithmic Results"],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2540090"],"URL":"https:\/\/doi.org\/10.1145\/2540090","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}