Computing a fixed point of a continuous function on a compact convex set is guaranteed to exist (by Brouwer's theorem) but hard to find. The computational complexity class PPAD captures this hardness: finding Nash equilibria, Kakutani fixed points, and other guaranteed-to-exist objects is PPAD-complete. In the worst case, no polynomial-time algorithm exists (unless PPAD = P).
Worst-case hardness is a strong statement — it says there exist pathological instances where fixed-point computation is intractable. But most instances encountered in practice are not pathological. The question: is the hardness typical or exceptional?
Smoothed analysis answers this by perturbing the input slightly — adding small random noise to the function defining the fixed-point problem. If the problem becomes easy after perturbation, the hardness was a property of carefully constructed worst-case instances, not of the problem's structure.
The paper shows that smoothed analysis does indeed make fixed-point computation tractable. After small random perturbation, polynomial-time algorithms succeed with high probability. The worst-case instances that make the problem PPAD-hard are measure-zero in the space of all instances — isolated pathologies that disappear under the slightest perturbation.
The structural point: PPAD-hardness is fragile. The fixed points exist robustly (Brouwer's theorem is topological and stable) but the computational hardness is brittle (it requires exact, unperturbed instances). The existence is structural; the difficulty is accidental. Equilibria are easy to find in practice because the hard instances are infinitely rare.