Abstract
| Original language | Undefined |
|---|---|
| Title of host publication | 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012 |
| Editors | B. Rovan, V. Sassone, P. Widmayer |
| Place of Publication | New York |
| Publisher | Springer |
| Pages | 198-209 |
| Number of pages | 12 |
| ISBN (Print) | 978-3-642-32588-5 |
| DOIs | |
| Publication status | Published - 2012 |
| Event | 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012 - Bratislava, Slovakia Duration: 27 Aug 2012 → 31 Aug 2012 Conference number: 37 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Volume | 7464 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012 |
|---|---|
| Abbreviated title | MFCS |
| Country | Slovakia |
| City | Bratislava |
| Period | 27/08/12 → 31/08/12 |
Keywords
- METIS-289632
- IR-80994
- Computational Complexity
- Smoothed Analysis
- EWI-21536
- average-case complexity
- Complexity Theory
Cite this
}
Smoothed complexity theory. / Bläser, Markus; Manthey, Bodo.
37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012. ed. / B. Rovan; V. Sassone; P. Widmayer. New York : Springer, 2012. p. 198-209 (Lecture Notes in Computer Science; Vol. 7464).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Smoothed complexity theory
AU - Bläser, Markus
AU - Manthey, Bodo
N1 - 10.1007/978-3-642-32589-2_20
PY - 2012
Y1 - 2012
N2 - Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng (J. ACM, 2004). Classical methods like worst-case or average-case analysis have accompanying complexity classes, like P and Avg−P, respectively. While worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allows us to talk about the inherent difficulty of problems. 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. We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first results.
AB - Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng (J. ACM, 2004). Classical methods like worst-case or average-case analysis have accompanying complexity classes, like P and Avg−P, respectively. While worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allows us to talk about the inherent difficulty of problems. 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. We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first results.
KW - METIS-289632
KW - IR-80994
KW - Computational Complexity
KW - Smoothed Analysis
KW - EWI-21536
KW - average-case complexity
KW - Complexity Theory
U2 - 10.1007/978-3-642-32589-2_20
DO - 10.1007/978-3-642-32589-2_20
M3 - Conference contribution
SN - 978-3-642-32588-5
T3 - Lecture Notes in Computer Science
SP - 198
EP - 209
BT - 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012
A2 - Rovan, B.
A2 - Sassone, V.
A2 - Widmayer, P.
PB - Springer
CY - New York
ER -