Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Smoothed Complexity Theory

Smoothed Complexity Theory 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. 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Smoothed Complexity Theory

Download PDF
21 pages

Loading next page...
 
/lp/association-for-computing-machinery/smoothed-complexity-theory-FlmI0iMzgw
Publisher
Association for Computing Machinery
Copyright
Copyright © 2015 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/2656210
Publisher site
See Article on Publisher Site

Abstract

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. 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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 11, 2015

Keywords: Smoothed analysis

References

  • Computational Complexity: A Modern Approach
    Arora, Sanjeev; Barak, Boaz
  • Smoothed analysis of the k-means method
    Arthur, David; Manthey, Bodo; Röglin, Heiko
  • Smoothed analysis of three combinatorial problems
    Banderier, Cyril; Beier, René; Mehlhorn, Kurt
  • Random knapsack in expected polynomial time
    Beier, René; Vöcking, Berthold
  • Typical properties of winners and losers in discrete optimization
    Beier, René; Vöcking, Berthold
  • On the theory of average case complexity
    Ben-David, Shai; Chor, Benny; Goldreich, Oded; Luby, Michael
  • Smoothed analysis of partitioning algorithms for Euclidean functionals
    Bläser, Markus; Manthey, Bodo; Rao, B. V. Raghavendra
  • Smoothed analysis of the perceptron algorithm for linear programming
    Blum, Avrim L.; Dunagan, John D.
  • Coloring random and semi-random k-colorable graphs
    Blum, Avrim L.; Spencer, Joel
  • Average-case complexity
    Bogdanov, Andrej; Trevisan, Luca
  • Adding random edges to dense graphs
    Bohman, Tom; Frieze, Alan M.; Krivelevich, Michael; Martin, Ryan
  • Smoothed analysis of belief propagation for minimum-cost flow and matching
    Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko
  • Smoothed analysis of the successive shortest path algorithm
    Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko
  • Improved smoothed analysis of multiobjective optimization
    Brunsch, Tobias; Röglin, Heiko
  • Settling the complexity of computing two-player Nash equilibria
    Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
  • Colouring semirandom graphs
    Coja-Oghlan, Amin
  • Solving NP-hard semirandom graph problems in polynomial expected time
    Coja-Oghlan, Amin
  • On smoothed k-CNF formulas and the walksat algorithm
    Coja-Oghlan, Amin; Feige, Uriel; Frieze, Alan M.; Krivelevich, Michael; Vilenchik, Dan
  • Smoothed analysis of left-to-right maxima with applications
    Damerow, Valentina; Manthey, Bodo; Heide, Friedhelm Meyer auf der; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till
  • Worst case and probabilistic analysis of the 2-opt algorithm for the TSP
    Englert, Matthias; Röglin, Heiko; Vöcking, Berthold
  • Refuting smoothed 3CNF formulas
    Feige, Uriel
  • Heuristics for semirandom graph problems
    Feige, Uriel; Kilian, Joe
  • On smoothed analysis of quicksort and Hoare’s find
    Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Jahromi, Nima Zeini
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
    Garey, Michael R.; Johnson, David S.
  • Average case completeness
    Gurevich, Yuri
  • Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63, 4, 512--530
    Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
  • On smoothed analysis in dense graphs and formulas
    Krivelevich, Michael; Sudakov, Benny; Tetali, Prasad
  • Average case complete problems
    Levin, Leonid A.
  • Average case complexity under the universal distribution equals worst-case complexity
    Li, Ming; Vitányi, Paul M. B.
  • An Introduction to Kolmogorov Complexity and Its Applications
    Li, Ming; Vitányi, Paul M. B.
  • Smoothed analysis of binary search trees
    Manthey, Bodo; Reischuk, Rüdiger
  • Smoothed analysis: Analysis of algorithms beyond worst case
    Manthey, Bodo; Röglin, Heiko
  • Worst-case and smoothed analysis of k-means clustering with Bregman divergences
    Manthey, Bodo; Röglin, Heiko
  • Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for Gaussian noise
    Manthey, Bodo; Veenstra, Rianne
  • Pareto optimal solutions for smoothed analysts
    Moitra, Ankur; O’Donnell, Ryan
  • Smoothed analysis of multiobjective optimization
    Röglin, Heiko; Teng, Shang-Hua
  • Smoothed analysis of integer programming
    Röglin, Heiko; Vöcking, Berthold
  • Smoothed analysis of termination of linear programming algorithms
    Spielman, Daniel A.; Teng, Shang-Hua
  • Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
    Spielman, Daniel A.; Teng, Shang-Hua
  • Smoothed analysis: An attempt to explain the behavior of algorithms in practice
    Spielman, Daniel A.; Teng, Shang-Hua
  • Beyond Hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method
    Vershynin, Roman
  • Average-case intractable NP problems
    Wang, Jie
  • Some examples of combinatorial averaging
    Wilf, Herbert S.