{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:20:18Z","timestamp":1759335618623,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":24,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214061","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"931-940","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Robust satisfiability of constraint satisfaction problems"],"prefix":"10.1145","author":[{"given":"Libor","family":"Barto","sequence":"first","affiliation":[{"name":"Charles University & McMaster University, Prague, Czech Rep"}]},{"given":"Marcin","family":"Kozik","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Krakow, Poland"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_3_2_2_2_1","volume-title":"Constraint satisfaction problems solvable by local consistency methods","author":"Barto L.","year":"2012","unstructured":"L. Barto and M. Kozik . Constraint satisfaction problems solvable by local consistency methods . 2012 . submitted. L. Barto and M. Kozik. Constraint satisfaction problems solvable by local consistency methods. 2012. submitted."},{"key":"e_1_3_2_2_3_1","volume-title":"Bounded relational width","author":"Bulatov A.","year":"2009","unstructured":"A. Bulatov . Bounded relational width . 2009 . manuscript. A. Bulatov. Bounded relational width. 2009. manuscript."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132547"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541893"},{"key":"e_1_3_2_2_8_1","volume-title":"Robust satisfiability for CSPs: algorithmic and hardness results","author":"Dalmau V.","year":"2011","unstructured":"V. Dalmau and A. Krokhin . Robust satisfiability for CSPs: algorithmic and hardness results . 2011 . in preparation. V. Dalmau and A. Krokhin. Robust satisfiability for CSPs: algorithmic and hardness results. 2011. in preparation."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_2_10_1","volume-title":"On Maltsev conditions associated with omitting certain types of local structures","author":"Freese R.","year":"2011","unstructured":"R. Freese , M. Kozik , A. Krokhin , M. Mar\u00f3ti , R. McKenzie , and R. Willard . On Maltsev conditions associated with omitting certain types of local structures . 2011 . in preparation. R. Freese, M. Kozik, A. Krokhin, M. Mar\u00f3ti, R. McKenzie, and R. Willard. On Maltsev conditions associated with omitting certain types of local structures. 2011. in preparation."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_2_12_1","first-page":"1574","volume-title":"Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set","author":"Guruswami V.","year":"2011","unstructured":"V. Guruswami and Y. Zhou . Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set . In D. Randall, editor, SODA, pages 1574 -- 1589 . SIAM , 2011 . V. Guruswami and Y. Zhou. Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. In D. Randall, editor, SODA, pages 1574--1589. SIAM, 2011."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.022"},{"key":"e_1_3_2_2_15_1","volume-title":"Explicit dimension reduction and its applications. Electronic Colloquium on Computational Complexity (ECCC), 16:121","author":"Karnin Z. S.","year":"2009","unstructured":"Z. S. Karnin , Y. Rabani , and A. Shpilka . Explicit dimension reduction and its applications. Electronic Colloquium on Computational Complexity (ECCC), 16:121 , 2009 . Z. S. Karnin, Y. Rabani, and A. Shpilka. Explicit dimension reduction and its applications. Electronic Colloquium on Computational Complexity (ECCC), 16:121, 2009."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_2_19_1","volume-title":"Linear programming, width-1 CSPs and robust satisfaction","author":"Kun G.","year":"2011","unstructured":"G. Kun , R. O'Donnell , S. Tamaki , Y. Yoshida , and Y. Zhou . Linear programming, width-1 CSPs and robust satisfaction . 2011 . manuscript. G. Kun, R. O'Donnell, S. Tamaki, Y. Yoshida, and Y. Zhou. Linear programming, width-1 CSPs and robust satisfaction. 2011. manuscript."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.048"},{"key":"e_1_3_2_2_21_1","volume-title":"Bounded width problems and algebras. Algebra Universalis, 56(3--4):439--466","author":"Larose B.","year":"2007","unstructured":"B. Larose and L. Z\u00e1dori . Bounded width problems and algebras. Algebra Universalis, 56(3--4):439--466 , 2007 . B. Larose and L. Z\u00e1dori. Bounded width problems and algebras. Algebra Universalis, 56(3--4):439--466, 2007."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276869"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York USA","acronym":"STOC'12"},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214061","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:56Z","timestamp":1750238456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":24,"alternative-id":["10.1145\/2213977.2214061","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214061","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}