{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:32Z","timestamp":1775184812093,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1145\/2488608.2488697","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"695-704","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["The complexity of finite-valued CSPs"],"prefix":"10.1145","author":[{"given":"Johan","family":"Thapper","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Sud 11, Paris, France"}]},{"given":"Stanislav","family":"Zivny","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-78835-7","volume-title":"Buildings -- Theory and Applications","author":"Abramenko P.","year":"2008","unstructured":"P. Abramenko and K. S. Brown . Buildings -- Theory and Applications , volume 248 of Graduate Texts in Mathematics . Springer , 2008 . P. Abramenko and K. S. Brown. Buildings -- Theory and Applications, volume 248 of Graduate Texts in Mathematics. Springer, 2008."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.25"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214061"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.003"},{"key":"e_1_3_2_1_10_1","volume-title":"July","author":"Cohen D. A.","year":"2012","unstructured":"D. A. Cohen , M. C. Cooper , P. Creed , P. Jeavons , and S. Zivn\u00fd . An algebraic theory of complexity for discrete optimisation. Technical report , July 2012 . arXiv:1207.6692. D. A. Cohen, M. C. Cooper, P. Creed, P. Jeavons, and S.Zivn\u00fd. An algebraic theory of complexity for discrete optimisation. Technical report, July 2012. arXiv:1207.6692."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11889205_10"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.04.002"},{"key":"e_1_3_2_1_13_1","series-title":"LNCS","first-page":"231","volume-title":"MFCS'11","author":"Cohen D. A.","year":"2011","unstructured":"D. A. Cohen , P. Creed , P. G. Jeavons , and S. Zivn\u00fd . An algebraic theory of complexity for valued constraints: Establishing a Galois connection . In MFCS'11 , volume 6907 of LNCS , pages 231 -- 242 . Springer , 2011 . D. A. Cohen, P. Creed, P. G. Jeavons, and S. Zivn\u00fd. An algebraic theory of complexity for valued constraints: Establishing a Galois connection. In MFCS'11, volume 6907 of LNCS, pages 231--242. Springer, 2011."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.02.003"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387933.2387943"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1205873"},{"key":"e_1_3_2_1_17_1","series-title":"LNCS","first-page":"210","volume-title":"CP'11","author":"Creed P.","year":"2011","unstructured":"P. Creed and S. Zivn\u00fd . On minimal weighted clones . In CP'11 , volume 6876 of LNCS , pages 210 -- 224 . Springer , 2011 . P. Creed and S. Zivn\u00fd. On minimal weighted clones. In CP'11, volume 6876 of LNCS, pages 210--224. Springer, 2011."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_3_2_1_19_1","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classification of Boolean Constraint Satisfaction Problems","author":"Creignou N.","year":"2001","unstructured":"N. Creignou , S. Khanna , and M. Sudan . Complexity Classification of Boolean Constraint Satisfaction Problems , volume 7 of SIAM Monographs on Discrete Mathematics and Applications . SIAM , 2001 . N. Creignou, S. Khanna, and M. Sudan. Complexity Classification of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, 2001."},{"key":"e_1_3_2_1_20_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_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391290"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29828-8_11"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_24_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_2"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_1_27_1","first-page":"1770","volume-title":"SODA'13","author":"Hirai H.","year":"2013","unstructured":"H. Hirai . Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems . In SODA'13 , pages 1770 -- 1778 . SIAM , 2013 . H. Hirai. Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems. In SODA'13, pages 1770--1778. SIAM, 2013."},{"key":"e_1_3_2_1_28_1","first-page":"1296","volume-title":"SODA'13","author":"Huber A.","year":"2013","unstructured":"A. Huber , A. Krokhin , and R. Powell . Skew Bisubmodularity and Valued CSPs . In SODA'13 , pages 1296 -- 1305 . SIAM , 2013 . A. Huber, A. Krokhin, and R. Powell. Skew Bisubmodularity and Valued CSPs. In SODA'13, pages 1296--1305. SIAM, 2013."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444644X"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.022"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669231"},{"key":"e_1_3_2_1_35_1","series-title":"LNCS","first-page":"438","volume-title":"CP'11","author":"Jonsson P.","year":"2011","unstructured":"P. Jonsson , F. Kuivinen , and J. Thapper . Min CSP on Four Elements: Moving Beyond Submodularity . In CP'11 , volume 6876 of LNCS , pages 438 -- 453 . Springer , 2011 . P. Jonsson, F. Kuivinen, and J. Thapper. Min CSP on Four Elements: Moving Beyond Submodularity. In CP'11, volume 6876 of LNCS, pages 438--453. Springer, 2011."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.19"},{"key":"e_1_3_2_1_38_1","volume-title":"July","author":"Kolmogorov V.","year":"2012","unstructured":"V. Kolmogorov . The power of linear programming for valued CSPs: a constructive characterization. Technical report , July 2012 . arXiv:1207.7213. V. Kolmogorov. The power of linear programming for valued CSPs: a constructive characterization. Technical report, July 2012. arXiv:1207.7213."},{"key":"e_1_3_2_1_39_1","first-page":"750","volume-title":"SODA'12","author":"Kolmogorov V.","year":"2012","unstructured":"% V. Kolmogorov and S. Zivn\u00fd . % The complexity of conservative valued CSPs . In SODA'12 , pages 750 -- 759 . SIAM, 2012 . Full version available on arXiv:1110.2809. %V. Kolmogorov and S. Zivn\u00fd.% The complexity of conservative valued CSPs. In SODA'12, pages 750--759. SIAM, 2012. Full version available on arXiv:1110.2809."},{"key":"e_1_3_2_1_40_1","first-page":"750","volume-title":"The complexity of conservative valued CSPs. Journal of the ACM, to appear. An extended abstract in SODA'12","author":"Kolmogorov V.","year":"2012","unstructured":"V. Kolmogorov and S. Zivn\u00fd . The complexity of conservative valued CSPs. Journal of the ACM, to appear. An extended abstract in SODA'12 , pages 750 -- 759 . SIAM , 2012 .% Full version available on arXiv:1110.2809. V. Kolmogorov and S. Zivn\u00fd. The complexity of conservative valued CSPs. Journal of the ACM, to appear. An extended abstract in SODA'12, pages 750--759. SIAM, 2012.% Full version available on arXiv:1110.2809."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_3_2_1_42_1","volume-title":"Oxford University Press","author":"Lauritzen S. L.","year":"1996","unstructured":"S. L. Lauritzen . Graphical Models . Oxford University Press , 1996 . S. L. Lauritzen. Graphical Models. Oxford University Press, 1996."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806790"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_48_1","volume-title":"Theory of linear and integer programming","author":"Schrijver A.","year":"1986","unstructured":"A. Schrijver . Theory of linear and integer programming . John Wiley & Sons, Inc. , 1986 . A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, Inc., 1986."},{"key":"e_1_3_2_1_49_1","series-title":"IAS\/Park City Mathematics Series","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1090\/pcms\/013\/08","volume-title":"Geometric Combinatorics","author":"Stanley R. P.","year":"2007","unstructured":"R. P. Stanley . An introduction to hyperplane arrangements . In E. Miller, V. Reiner, and B. Sturmfels, editors, Geometric Combinatorics , volume 13 of IAS\/Park City Mathematics Series , pages 389 -- 496 . AMS , Providence, RI , 2007 . R. P. Stanley. An introduction to hyperplane arrangements. In E. Miller, V. Reiner, and B. Sturmfels, editors, Geometric Combinatorics, volume 13 of IAS\/Park City Mathematics Series, pages 389--496. AMS, Providence, RI, 2007."},{"key":"e_1_3_2_1_50_1","first-page":"657","volume-title":"STACS'10","author":"Takhanov R.","year":"2010","unstructured":"R. Takhanov . A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem . In STACS'10 , pages 657 -- 668 , 2010 . R. Takhanov. A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem. In STACS'10, pages 657--668, 2010."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.25"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488697","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488697","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:20Z","timestamp":1750235960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488697"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":51,"alternative-id":["10.1145\/2488608.2488697","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488697","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}