Solving Polynomial Equations in Smoothed Polynomial Time
summary
Shows that adaptive linear homotopy with Newton steps and randomized start sampling has a provable smooth‑analysis bound: the expected continuation cost reduces to an integral of the squared condition number and local Gaussian perturbations give a bound of order O(n / sigma^2) for the mean square condition number. Consequences: the Las Vegas homotopy runs in smoothed polynomial time, and a deterministic algorithm achieves expected time N^{o(log log N)} on dense inputs and true polynomial time for bounded‑degree (e.g. quadratic) systems.
AI-written summary · about