{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:45Z","timestamp":1750306725609,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T00:00:00Z","timestamp":1431302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG research","award":["BL 511\/7-1"],"award-info":[{"award-number":["BL 511\/7-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,5,11]]},"abstract":"<jats:p>Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng. Classical methods like worst-case or average-case analysis have accompanying complexity classes, such as P and Avg-P, respectively. Whereas worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allow us to talk about the inherent difficulty of problems.<\/jats:p>\n          <jats:p>Smoothed analysis is a hybrid of worst-case and average-case analysis and compensates some of their drawbacks. Despite its success for the analysis of single algorithms and problems, there is no embedding of smoothed analysis into computational complexity theory, which is necessary to classify problems according to their intrinsic difficulty.<\/jats:p>\n          <jats:p>We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first hardness results (of bounded halting and tiling) and tractability results (binary optimization problems, graph coloring, satisfiability) within this framework.<\/jats:p>","DOI":"10.1145\/2656210","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T12:18:00Z","timestamp":1431433080000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Smoothed Complexity Theory"],"prefix":"10.1145","volume":"7","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[{"name":"Saarland University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[{"name":"University of Twente, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,11]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1017\/CBO9780511804090"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/2027216.2027217"},{"key":"e_1_2_1_3_1","volume-title":"Mathematical Foundations of Computer Science","author":"Banderier Cyril","year":"2003","unstructured":"Cyril Banderier , Ren\u00e9 Beier , and Kurt Mehlhorn . 2003. Smoothed analysis of three combinatorial problems . In Mathematical Foundations of Computer Science 2003 . Lecture Notes in Computer Science, Vol. 2747 . Springer , 198--207. Cyril Banderier, Ren\u00e9 Beier, and Kurt Mehlhorn. 2003. Smoothed analysis of three combinatorial problems. In Mathematical Foundations of Computer Science 2003. Lecture Notes in Computer Science, Vol. 2747. Springer, 198--207."},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/j.jcss.2004.04.004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1137\/S0097539705447268"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/0022-0000(92)90019-F"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/s00453-012-9643-5"},{"key":"e_1_2_1_8_1","volume-title":"Dunagan","author":"Blum Avrim L.","year":"2002","unstructured":"Avrim L. Blum and John D . Dunagan . 2002 . Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). 905--914. Avrim L. Blum and John D. Dunagan. 2002. Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). 905--914."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1006\/jagm.1995.1034"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1561\/0400000004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1002\/rsa.10112"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.7155\/jgaa.00310"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.5555\/2627817.2627902"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/2699445"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1516512.1516516"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1017\/S0963548306007917"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/j.jalgor.2004.07.003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.5555\/1496770.1496820"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/2229163.2229174"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/s00453-013-9801-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/FOCS.2007.59"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1006\/jcss.2001.1773"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/s00453-011-9490-9"},{"key":"e_1_2_1_24_1","volume-title":"Johnson","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 and Company , New York, NY. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, NY."},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1016\/0022-0000(91)90007-R"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1006\/jcss.2001.1774"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1002\/rsa.v29:2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1137\/0215020"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1016\/0020-0190(92)90138-L"},{"key":"e_1_2_1_30_1","volume-title":"Vit\u00e1nyi","author":"Li Ming","year":"1993","unstructured":"Ming Li and Paul M. B . Vit\u00e1nyi . 1993 . An Introduction to Kolmogorov Complexity and Its Applications. Springer , New York, NY. Ming Li and Paul M. B. Vit\u00e1nyi. 1993. An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, NY."},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1016\/j.tcs.2007.02.035"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1524\/itit.2011.0654"},{"key":"e_1_2_1_33_1","first-page":"94","article-title":"Worst-case and smoothed analysis of k-means clustering with Bregman divergences","volume":"4","author":"Manthey Bodo","year":"2013","unstructured":"Bodo Manthey and Heiko R\u00f6glin . 2013 . Worst-case and smoothed analysis of k-means clustering with Bregman divergences . Journal of Computational Geometry 4 , 1, 94 -- 132 . Bodo Manthey and Heiko R\u00f6glin. 2013. Worst-case and smoothed analysis of k-means clustering with Bregman divergences. Journal of Computational Geometry 4, 1, 94--132.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computation","author":"Manthey Bodo","unstructured":"Bodo Manthey and Rianne Veenstra . 2013. Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for Gaussian noise . In Algorithms and Computation . Lecture Notes in Computer Science , Vol. 8283 . Springer , 579--589. Bodo Manthey and Rianne Veenstra. 2013. Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for Gaussian noise. In Algorithms and Computation. Lecture Notes in Computer Science, Vol. 8283. Springer, 579--589."},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/1993636.1993667"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1109\/FOCS.2009.21"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1007\/s10107-006-0055-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1007\/s10107-003-0448-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/990308.990310"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/1562764.1562785"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1137\/070683386"},{"volume-title":"Advances in Languages, Algorithms, and Complexity, D.-Z. Du and K.-I. Ko (Eds.)","author":"Wang Jie","unstructured":"Jie Wang . 1997. Average-case intractable NP problems . In Advances in Languages, Algorithms, and Complexity, D.-Z. Du and K.-I. Ko (Eds.) . Kluwer , Dordrecht, Netherlands , 313--378. Jie Wang. 1997. Average-case intractable NP problems. In Advances in Languages, Algorithms, and Complexity, D.-Z. Du and K.-I. Ko (Eds.). Kluwer, Dordrecht, Netherlands, 313--378.","key":"e_1_2_1_42_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1080\/00029890.1985.11971591"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656210","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2656210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:37Z","timestamp":1750231177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2656210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,11]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,11]]}},"alternative-id":["10.1145\/2656210"],"URL":"https:\/\/doi.org\/10.1145\/2656210","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2015,5,11]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}