Smoothed complexity theory

Markus Bläser, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageUndefined
Title of host publication37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012
EditorsB. Rovan, V. Sassone, P. Widmayer
Place of PublicationNew York
PublisherSpringer
Pages198-209
Number of pages12
ISBN (Print)978-3-642-32588-5
DOIs
Publication statusPublished - 2012
Event37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012 - Bratislava, Slovakia
Duration: 27 Aug 201231 Aug 2012
Conference number: 37

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume7464
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012
Abbreviated titleMFCS
CountrySlovakia
CityBratislava
Period27/08/1231/08/12

Keywords

  • METIS-289632
  • IR-80994
  • Computational Complexity
  • Smoothed Analysis
  • EWI-21536
  • average-case complexity
  • Complexity Theory

Cite this