Smoothed analysis of algorithms

Daniel A. Spielman, Shang‐Hua Teng

Type: Article

Publication Date: 2004-05-01

Citations: 827

DOI: https://doi.org/10.1145/990308.990310

View Publication

Locations

Journal of the ACM - View

Similar Works

Action	Title	Year	Authors
+	Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time	2001	Daniel A. Spielman Shang‐Hua Teng
+	Smoothed analysis of algorithms	2002	Daniel A. Spielman Shang‐Hua Teng
+	The Smoothed Analysis of Algorithms	2005	Daniel A. Spielman
+	Smoothed analysis of the perceptron algorithm for linear programming	2002	Avrim Blum John Dunagan
+	Smoothed Complexity Theory	2012	Markus Bläser Bodo Manthey
+	Smoothed Complexity Theory	2012	Markus Bläser Bodo Manthey
+ PDF Chat	Smoothed Complexity Theory	2015	Markus Bläser Bodo Manthey
+	Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method	2023	Sophie Huiberts Yin Tat Lee Xinzhi Zhang
+	Analysis of Algorithms	2021	Xin‐She Yang
+	Beyond the Worst-Case Analysis of Algorithms (Introduction)	2020	Tim Roughgarden
+	Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.	2007	Bodo Manthey Till Tantau
+	A Machine Learning Approach to Predicting the Smoothed Complexity of Sorting Algorithms	2015	Bichen Shi Michel Schellekens Georgiana Ifrim
+ PDF Chat	Smoothed analysis of termination of linear programming algorithms	2003	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Complexity analysis of random convex hulls	2015	Rémy Thomasse
+ PDF Chat	Smoothed Analysis with Adaptive Adversaries	2022	Nika Haghtalab Tim Roughgarden Abhishek Shetty
+	Smoothed Analysis of Dynamic Networks	2015	Michael Dinitz Jeremy T. Fineman Seth Gilbert Calvin Newport
+	Smoothed Analysis of Dynamic Networks	2015	Michael Dinitz Jeremy T. Fineman Seth Gilbert Calvin Newport
+	k-Means has Polynomial Smoothed Complexity	2009	David Arthur Bodo Manthey Heiko Röglin
+	Smoothed Analysis of Interior-Point Algorithms: Condition Number	2003	John Dunagan Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	A friendly smoothed analysis of the simplex method	2018	Daniel Dadush Sophie Huiberts

Works That Cite This (439)

Action	Title	Year	Authors
+	Smoothed analysis for the condition number of structured real polynomial systems	2021	Alperen A. Ergür Grigoris Paouris J. Maurice Rojas
+	Polynomial time guarantees for the Burer-Monteiro method	2019	Diego Cifuentes Ankur Moitra
+ PDF Chat	Nonnegative Matrix Factorization	2018	Roland Badeau Tuomas Virtanen
+	The Unavoidable Condition… A Report on the Book	2015	Jean-Claude Yakoubsohn
+ PDF Chat	Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit	2008	Deanna Needell Roman Vershynin
+ PDF Chat	RANDOM MATRICES: THE CIRCULAR LAW	2008	Terence Tao Van Vu
+	Nearly optimal minimax estimator for high-dimensional sparse linear regression	2013	Li Zhang
+	Random Matrices: The circular Law	2007	Terence Tao Van Vu
+	Spectral functions and smoothing techniques on Jordan algebras	2006	Michel Baes
+ PDF Chat	Bounded-Degree Spanning Trees in Randomly Perturbed Graphs	2017	Michael Krivelevich Matthew Kwan Benny Sudakov

Works Cited by This (38)

Action	Title	Year	Authors
+	Smoothed Analysis of Renegar’s Condition Number for Linear Programming	2002	John Dunagan Daniel A. Spielman Shang‐Hua Teng
+	Eigenvalue Roulette and Random Test Matrices	1993	Alan Edelman
+	HOW GOOD IS THE SIMPLEX ALGORITHM	1970	Victor Klee George J. Minty
+	Notes on Bland’s pivoting rule	1978	David Avis Vašek Chvátal
+	Heuristics for finding large independent sets, with applications to coloring semi-random graphs	2002	Uriel Feige Joe Kilian
+ PDF Chat	Eigenvalues and Condition Numbers of Random Matrices	1988	Alan Edelman
+ PDF Chat	Linear programming, complexity theory and elementary functional analysis	1995	James Renegar
+	On the average number of steps of the simplex method of linear programming	1983	Steve Smale
+ PDF Chat	Incorporating Condition Measures into the Complexity Theory of Linear Programming	1995	James Renegar
+	Some Applications of the Rank Revealing QR Factorization	1992	Tony F. Chan Per Christian Hansen