{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:13Z","timestamp":1761621013952,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2009,5,31]],"date-time":"2009-05-31T00:00:00Z","timestamp":1243728000000},"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":[[2009,5,31]]},"DOI":"10.1145\/1536414.1536512","type":"proceedings-article","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T14:51:13Z","timestamp":1243954273000},"page":"725-734","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["A new line of attack on the dichotomy conjecture"],"prefix":"10.1145","author":[{"given":"G\u00e1bor","family":"Kun","sequence":"first","affiliation":[{"name":"IAS, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[{"name":"Rutgers, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,5,31]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"e_1_3_2_1_2_1","unstructured":". Barto M. Kozik Constraint Satisfaction Problems of bounded width manuscript.  . Barto M. Kozik Constraint Satisfaction Problems of bounded width manuscript."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.50"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"volume-title":"Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003)","year":"2003","key":"e_1_3_2_1_5_1","unstructured":". Bulatov, Tractable conservative constraint satisfaction problems , Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003) , ( 2003 ), 321--330. . Bulatov, Tractable conservative constraint satisfaction problems, Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), (2003), 321--330."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_3_2_1_8_1","volume-title":"Sci., 1853","author":"Bulatov P.","year":"2002","unstructured":". Bulatov , P. Jeavons , A. A. Krokhin, Constraint satisfaction problems and finite algebras, Automata, languages and programming (Geneva, 2001), Lecture notes in Comput . Sci., 1853 ,Springer, Berlin , ( 2002 ), 272--282. . Bulatov, P. Jeavons, A. A. Krokhin, Constraint satisfaction problems and finite algebras, Automata, languages and programming (Geneva, 2001), Lecture notes in Comput. Sci., 1853,Springer, Berlin, (2002), 272--282."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1643275.1643306"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_1_11_1","unstructured":". Dalmau Generalized majority-minority operations are tractable LICS05.  . Dalmau Generalized majority-minority operations are tractable LICS05."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"volume-title":"CP'99","author":"Dalmau J.","key":"e_1_3_2_1_13_1","unstructured":". Dalmau and J. Pearson , Set Functions and Width 1 Problems, Principles and Practice of Constraint Programming , CP'99 . . Dalmau and J. Pearson, Set Functions and Width 1 Problems, Principles and Practice of Constraint Programming, CP'99."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132553"},{"key":"e_1_3_2_1_15_1","unstructured":"rit Dinur Ehud Friedgut Oded Regev Independent Sets in Graph Powers are Almost Contained in Juntas Geometric and Functional Analysis accepted.  rit Dinur Ehud Friedgut Oded Regev Independent Sets in Graph Powers are Almost Contained in Juntas Geometric and Functional Analysis accepted."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.017"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_2_1_19_1","volume-title":"Constraint Satisfaction and Complexity, manuscript","author":"Hell J.","year":"2008","unstructured":". Hell , J. Nesetril , Colouring , Constraint Satisfaction and Complexity, manuscript , 2008 . http:\/\/iti.mff.cuni.cz\/series\/files\/iti413.eps . Hell, J. Nesetril, Colouring, Constraint Satisfaction and Complexity, manuscript, 2008. http:\/\/iti.mff.cuni.cz\/series\/files\/iti413.eps"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-96-01537-1"},{"key":"e_1_3_2_1_21_1","unstructured":". Kun Constraints MMSNP and expanderrelational structures Combinatorica submitted.  . Kun Constraints MMSNP and expanderrelational structures Combinatorica submitted."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.027"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_3_2_1_24_1","volume-title":"Omitting types, bounded width and the ability to count, manuscript","author":"Larose L.","year":"2008","unstructured":". Larose , L. Z\u00e1dori , M. Valeriote , Omitting types, bounded width and the ability to count, manuscript , 2008 . . Larose, L. Z\u00e1dori, M. Valeriote, Omitting types, bounded width and the ability to count, manuscript, 2008."},{"key":"e_1_3_2_1_25_1","unstructured":". McKenzie M. Mar\u00f3ti: Existence theorems for weakly symmetric operations Algebra Universalis to appear.  . McKenzie M. Mar\u00f3ti: Existence theorems for weakly symmetric operations Algebra Universalis to appear."},{"key":"e_1_3_2_1_26_1","volume-title":"manuscript","author":"Nesetril M.","year":"2007","unstructured":". Nesetril , M. Siggers , L. Z\u00e1dori :ph A Combinatorial constraint satisfaction problem dichotomy classification conjecture , manuscript , 2007 . . Nesetril, M. Siggers, L. Z\u00e1dori:phA Combinatorial constraint satisfaction problem dichotomy classification conjecture, manuscript, 2007."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/244715.244724"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267761"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010676831037"}],"event":{"name":"STOC '09: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Bethesda MD USA","acronym":"STOC '09"},"container-title":["Proceedings of the forty-first annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1536414.1536512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1536414.1536512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:51Z","timestamp":1750253931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1536414.1536512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,31]]},"references-count":30,"alternative-id":["10.1145\/1536414.1536512","10.1145\/1536414"],"URL":"https:\/\/doi.org\/10.1145\/1536414.1536512","relation":{},"subject":[],"published":{"date-parts":[[2009,5,31]]},"assertion":[{"value":"2009-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}