Smoothed Complexity Theory

Markus Bläser, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
2 Downloads (Pure)


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. 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.
Original languageEnglish
Pages (from-to)6
Number of pages21
JournalACM transactions on computation theory
Issue number2
Publication statusPublished - May 2015


  • average-case complexity
  • EWI-25293
  • METIS-312453
  • Computational Complexity
  • Smoothed Analysis
  • IR-95820
  • 2023 OA procedure


Dive into the research topics of 'Smoothed Complexity Theory'. Together they form a unique fingerprint.

Cite this