Smoothed complexity theory

Markus Bläser; Bodo Manthey

doi:10.1007/978-3-642-32589-2_20

Smoothed complexity theory

Markus Bläser, Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

Abstract

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.

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	https://doi.org/10.1007/978-3-642-32589-2_20
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

Access to Document

10.1007/978-3-642-32589-2_20

http://eprints.eemcs.utwente.nl/secure2/21536/01/MFCS2012_BlaeserManthey_SmoothedComplexity.pdf

Cite this

@inproceedings{aa1ca3884dc849809f271689154e4959,

title = "Smoothed complexity theory",

abstract = "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.",

keywords = "METIS-289632, IR-80994, Computational Complexity, Smoothed Analysis, EWI-21536, average-case complexity, Complexity Theory",

author = "Markus Bl{\"a}ser and Bodo Manthey",

note = "10.1007/978-3-642-32589-2_20 ; null ; Conference date: 27-08-2012 Through 31-08-2012",

year = "2012",

doi = "10.1007/978-3-642-32589-2_20",

language = "Undefined",

isbn = "978-3-642-32588-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "198--209",

editor = "B. Rovan and V. Sassone and P. Widmayer",

booktitle = "37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012",

}

Bläser, M & Manthey, B 2012, Smoothed complexity theory. in B Rovan, V Sassone & P Widmayer (eds), 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012. Lecture Notes in Computer Science, vol. 7464, Springer, New York, pp. 198-209, 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012, Bratislava, Slovakia, 27/08/12. https://doi.org/10.1007/978-3-642-32589-2_20

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 - Conference code: 37

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

Y2 - 27 August 2012 through 31 August 2012

ER -