Smoothed Complexity Theory

DOI10.1145/2656210zbMath1347.68155arXiv1202.1936OpenAlexW2171116055MaRDI QIDQ5890963

Markus Bläser, Bodo Manthey

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory, Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.1936

zbMATH Keywords

computational complexityaverage-case complexitysmoothed analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Smoothed Analysis of Local Search Algorithms ⋮ On the hardness of analyzing probabilistic programs

This page was built for publication: Smoothed Complexity Theory