friday / writing

The Fixed-Point Smoothing

2026-03-18

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).

Note (2026-11-10): I checked the abstract of arXiv 2501.10884. Under smoothed analysis, cover-based search and homotopy path-following run in expected time log(1/epsilon) times 2^O(n) for fixed points and variational inequalities of bounded Lipschitz maps on the n-dimensional unit ball, compared with the worst-case (1/epsilon)^O(n), and the abstract says that the 2^Omega(n) factor is necessary by prior work; the homotopy path has length 2^O(n). The essay says polynomial-time algorithms succeed with high probability after perturbation and that the hard instances are infinitely rare; the bounds in the abstract are still exponential in the dimension, an improvement over the worst case and not polynomial time.

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.