Smoothed Analysis of Algorithms

Spielman and Teng [STOC '01] introduced the smoothed analysis of al­ gorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could not be understood through the traditional worst-case and average-case analyses. In this talk, we survey some of the smoothed analyses that have been performed.

• Publication year

  2002

• Venue

  arXiv: Optimization and Control

• Publication date

  2002-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv math/0212413
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Smoothed Analysis of Interior-Point Algorithms: Condition Number

  2003cited by this paper
• Smoothed analysis of the perceptron algorithm for linear programming

  2002cited by this paper
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

  2001influential reference
• Complexity theory and numerical analysis

  1997cited by this paper
• Applied Numerical Linear Algebra

  1997cited by this paper
• Deformed products and maximal shadows of polytopes

  1996cited by this paper
• On the probability that a random ±1-matrix is singular

  1995cited by this paper
• Incorporating Condition Measures into the Complexity Theory of Linear Programming

  1995cited by this paper
• Linear programming, complexity theory and elementary functional analysis

  1995cited by this paper
• Some perturbation theory for linear programming

  1994cited by this paper
• Eigenvalues and condition numbers of random matrices

  1988cited by this paper
• A simplex variant solving an m times d linear program in O(min(m2, d2) expected number of pivot steps

  1987cited by this paper
• The Simplex Method: A Probabilistic Analysis

  1986cited by this paper
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

  1986cited by this paper
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

  1985cited by this paper
• On the average number of steps of the simplex method of linear programming

  1983cited by this paper
• Computational complexity of parametric linear programming

  1980cited by this paper
• Worst case behavior of the steepest edge simplex method

  1979cited by this paper
• Notes on Bland’s pivoting rule

  1978cited by this paper
• The simplex algorithm with the pivot rule of maximizing criterion improvement

  1973cited by this paper
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper

• Inhomogeneous symmetric random matrix: eigenvalues and eigenvectors

  2025cites this paper
• Probabilistic combinatorics at exponentially small scales

  2025influential citation
• Singularity of biased discrete random matrix

  2025cites this paper
• The smallest singular value of sparse discrete random matrices

  2025cites this paper
• The Rank and Singular Values of the Inhomogeneous Subgaussian Random Matrices

  2024cites this paper
• Quantitative estimates of the singular values of random i.i.d. matrices

  2024cites this paper
• Stochastic Rounding 2.0, with a View towards Complexity Analysis

  2024cites this paper
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

  2024cites this paper
• On the Spielman-Teng Conjecture

  2024cites this paper
• The Complexity of Diagonalization

  2023cites this paper
• The Societal Impacts of Algorithmic Decision-Making

  2023cites this paper
• Oblivious Markov Decision Processes: Planning and Policy Execution

  2023cites this paper
• “Intelligent Heuristics Are the Future of Computing”

  2023cites this paper
• Synthesis of and compilation with time-optimal multi-qubit gates

  2022cites this paper
• Phase transition of eigenvalues in deformed Ginibre ensembles I: GinUE

  2022cites this paper
• Approximate Real Symmetric Tensor Rank

  2022cites this paper
• The Smoothed Complexity of Policy Iteration for Markov Decision Processes

  2022cites this paper
• Lift, Partition, and Project: Parametric Complexity Certification of Active-Set QP Methods in the Presence of Numerical Errors

  2022cites this paper
• Speeding up random walk mixing by starting from a uniform vertex

  2022cites this paper
• Approximate Low-Rank Decomposition for Real Symmetric Tensors

  2022cites this paper
• A p-adic Descartes solver: the Strassman solver

  2022cites this paper
• Fair Allocations for Smoothed Utilities

  2022cites this paper
• Extending generalized unsupervised manifold alignment

  2022cites this paper
• Quantitative invertibility of non-Hermitian random matrices

  2022influential citation
• Asymptotic Density and Computability

  2021cites this paper
• Distribution of the Scaled Condition Number of Single-Spiked Complex Wishart Matrices

  2021cites this paper
• A Riemann-Hilbert approach to the perturbation theory for orthogonal polynomials: Applications to numerical linear algebra and random matrix theory

  2021cites this paper
• The conjugate gradient algorithm on a general class of spiked covariance matrices

  2021cites this paper
• Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model

  2021cites this paper
• Smoothed Differential Privacy

  2021cites this paper
• On the condition number of the shifted real Ginibre ensemble

  2021cites this paper
• The Smallest Singular Value of a Shifted Random Matrix

  2021cites this paper
• A numerical algorithm for zero counting. IV: An adaptive speedup

  2021cites this paper
• Matrix anti-concentration inequalities with applications

  2021cites this paper
• What else is leaked when eavesdropping Federated Learning?

  2021cites this paper
• On the Complexity of Load Balancing in Dynamic Networks

  2021cites this paper
• Best-Fit Subspaces and Singular Value Decomposition (SVD)

  2020cites this paper
• Other Topics

  2020cites this paper
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity

  2020cites this paper
• Introduction

  2020cites this paper
• High-Dimensional Space

  2020cites this paper
• Topic Models, Nonnegative Matrix Factorization, Hidden Markov Models, and Graphical Models

  2020cites this paper
• Index

  2020cites this paper
• Wavelets

  2020cites this paper
• Random Walks and Markov Chains

  2020cites this paper
• Algorithms for Massive Data Problems: Streaming, Sketching, and Sampling

  2020cites this paper
• On the smoothed analysis of the smallest singular value with discrete noise

  2020cites this paper
• Polynomial-time Trace Reconstruction in the Smoothed Complexity Model

  2020cites this paper
• List-wise Fairness Criterion for Point Processes

  2020cites this paper
• Condition numbers for the cube. I: Univariate polynomials and hypersurfaces

  2020cites this paper
• On the Complexity of the Plantinga–Vegter Algorithm

  2020influential citation
• Universal Average-Case Optimality of Polyak Momentum

  2020cites this paper
• Plantinga-Vegter Algorithm takes Average Polynomial Time

  2019cites this paper
• Energy Efficient Cooperative Computation Algorithm in Energy Harvesting Internet of Things

  2019cites this paper
• Smoothing the gap between NP and ER

  2019cites this paper
• Fair Division with Bounded Sharing: Binary and Non-degenerate Valuations

  2019cites this paper
• Universality of the least singular value for the sum of random matrices

  2019cites this paper
• The genus of the Erdős‐Rényi random graph and the fragile genus property

  2019cites this paper
• Background Material

  2019cites this paper
• Condition and homology in semialgebraic geometry

  2019cites this paper
• Stabilize deep ResNet with a sharp scaling factor τ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau$$\end{document

  2019cites this paper
• Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm

  2018cites this paper
• Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis

  2018cites this paper
• The smallest singular value of a shifted d-regular random square matrix

  2018cites this paper
• Algorithmic Aspects of Machine Learning

  2018cites this paper
• Relaxing the strong triadic closure problem for edge strength inference

  2018cites this paper
• Smoothed analysis for the condition number of structured real polynomial systems

  2018cites this paper
• AROUND THE CIRCULAR

  2018cites this paper
• Invertibility via distance for noncentered random matrices with continuous distributions

  2017cites this paper
• Universality for Eigenvalue Algorithms on Sample Covariance Matrices

  2017cites this paper
• The smallest singular value of a shifted d-regular random square matrix

  2017cites this paper
• Random matrices: repulsion in spectrum

  2017influential citation
• Random matrices: Overcrowding estimates for the spectrum

  2017cites this paper
• A friendly smoothed analysis of the simplex method

  2017cites this paper
• Edinburgh Research Explorer Coverage Processes on Spheres and Conditions Numbers for Linear Programming

  2017cites this paper
• Universality of the least singular value for sparse random matrices

  2017cites this paper
• Probabilistic analyses of condition numbers*

  2016cites this paper
• Weakly Random Additive Preconditioning for Matrix Computations ∗

  2016cites this paper
• Smoothed Analysis for the Conjugate Gradient Algorithm

  2016cites this paper
• The smallest singular value of random rectangular matrices with no moment assumptions on entries

  2016cites this paper
• Spectral statistics of non-selfadjoint operators subject to small random perturbations

  2016cites this paper
• The Unavoidable Condition… A Report on the Book

  2015cites this paper
• Random matrices: tail bounds for gaps between eigenvalues

  2015cites this paper
• Holding-time-aware dynamic traffic grooming algorithms based on multipath routing for WDM optical networks

  2015cites this paper
• k-center Clustering under Perturbation Resilience

  2015cites this paper
• A Machine Learning Approach to Predicting the Smoothed Complexity of Sorting Algorithms

  2015cites this paper
• On Singular Values of Random Matrices

  2015cites this paper
• Probabilistic Estimates of the Largest Strictly Convex Singular Values of Pregaussian Random Matrices

  2015cites this paper
• A stable, polynomial-time algorithm for the eigenpair problem

  2014cites this paper
• ON A CONDITION NUMBER OF RANDOM POLYNOMIAL SYSTEMS

  2014influential citation
• Smallest Singular Value for Perturbations of Random Permutation Matrices

  2014cites this paper
• Gordon's inequality and condition numbers in conic optimization

  2014cites this paper
• The smallest singular value of random rectangular matrices with no moment assumptions on entries

  2014cites this paper
• Outlier Eigenvalues for Deformed I.I.D. Random Matrices

  2014cites this paper
• Recent developments in non-asymptotic theory of random matrices

  2013influential citation
• The Simplex Algorithm Is NP-Mighty

  2013cites this paper
• Condition - The Geometry of Numerical Algorithms

  2013cites this paper
• Randomized preprocessing versus pivoting

  2013cites this paper
• Small Ball Probability, Inverse Theorems, and Applications

  2012influential citation
• SMALL PROBABILITY , INVERSE THEOREMS , AND APPLICATIONS

  2012influential citation