Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem

DOI10.1145/1806689.1806759zbMath1293.68161OpenAlexW2076927517WikidataQ57733129 ScholiaQ57733129MaRDI QIDQ2875178

Felipe Cucker, Peter Bürgisser

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806759

zbMATH Keywords

complexityapproximate zeropolynomial timehomotopy methodspolynomial equation solvingsmoothed analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem