Smoothed analysis of algorithms
arXiv:math/0212413
Abstract
Spielman and Teng introduced the smoothed analysis of algorithms 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.
Cited by in corpus (26)
- The probability that a small perturbation of a numerical analysis problem is difficult
- A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis
- Random Matrices: The circular Law
- Toward accurate polynomial evaluation in rounded arithmetic
- Gordon's inequality and condition numbers in conic optimization
- Random matrices: tail bounds for gaps between eigenvalues
- The Littlewood-Offord Problem and invertibility of random matrices
- Random matrices: The distribution of the smallest singular values
- Smoothed Analysis for the Conjugate Gradient Algorithm
- A stable, polynomial-time algorithm for the eigenpair problem
- Universality of the least singular value for the sum of random matrices
- Robust Smoothed Analysis of a Condition Number for Linear Programming
- Smoothed analysis of complex conic condition numbers
- On a Problem Posed by Steve Smale
- Adversarial Smoothed Analysis
- The smallest singular value of random rectangular matrices with no moment assumptions on entries
- Random matrices: overcrowding estimates for the spectrum
- The condition number of a randomly perturbed matrix
- Smallest Singular Value for Perturbations of Random Permutation Matrices
- Universality of the least singular value for sparse random matrices
- Universality for eigenvalue algorithms on sample covariance matrices
- On a condition number of random polynomial systems
- Smoothed analysis of componentwise condition numbers for sparse matrices
- Smoothed analysis of symmetric random matrices with continuous distributions
- From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices
- A randomized Kaczmarz algorithm with exponential convergence