smoothed analysis
There is a famous puzzle in algorithms. The simplex method for linear programming is, in theory, exponential in the worst case — yet for sixty years it has been one of the fastest, most reliable methods in actual practice, almost never showing its bad behavior. Worst-case analysis screams 'avoid it!'; average-case analysis is hard to trust because it assumes inputs are drawn from some idealized random distribution that real life ignores. Smoothed analysis is the brilliant compromise that resolves the paradox: it asks not 'how bad is the absolute worst input?' nor 'how good is a purely random input?', but 'how does the algorithm do on a worst-case input that is then slightly, randomly perturbed?'.
Precisely: take any input you like — even the most adversarial one — and then jiggle it by a small random amount (add tiny random noise of magnitude controlled by a parameter sigma to each number). The smoothed running time is the EXPECTED running time over that random perturbation, and then we take the worst case over the original (un-perturbed) input. An algorithm has good smoothed complexity if this quantity is small (say, polynomial) for every starting input, as long as a little noise is added. The picture: worst-case running time looks at isolated, razor-thin spikes of difficulty in the space of inputs; perturbing smears each input over a small neighborhood, and if the nasty spikes are rare and fragile, the tiny random nudge almost always lands you off them. Spielman and Teng proved exactly this for simplex: its smoothed running time is polynomial, so the bad cases are so delicately balanced that any real-world imprecision (measurement noise, rounding) destroys them.
Smoothed analysis matters because it bridges theory and practice: it explains, rigorously, why algorithms with terrible worst cases (simplex, certain local-search methods, some integer-programming heuristics) work beautifully on the slightly-noisy inputs the real world actually produces. It is a flagship of the 'beyond worst-case analysis' movement, which seeks models more faithful to real inputs than the pessimistic worst case. The honest caveats: smoothed analysis is a hybrid measure, not a pure guarantee on every fixed input — a specific un-perturbed input can still be slow, the claim is about the perturbed average; the conclusion depends on the noise model and magnitude sigma you assume (too little noise and the worst case returns); and it explains good practical behavior, it does not make a worst-case-exponential algorithm worst-case-polynomial.
The simplex method can be forced into exponential time by adversarial linear programs (e.g. Klee-Minty cubes). But those bad instances are knife-edge: perturb each coefficient by tiny random noise and the exponential behavior almost surely vanishes. Spielman and Teng proved simplex's smoothed running time is polynomial — explaining sixty years of it being fast in practice despite a fearsome worst case.
Smoothed = worst case over inputs, then average over tiny random perturbation: fragile bad cases vanish.
Smoothed analysis is a HYBRID (worst-case input, then averaged over a small random perturbation), not a per-input guarantee — a specific un-perturbed input can still be slow. The conclusion depends on the assumed noise magnitude sigma; with too little noise, the bad worst case returns.