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

DOI10.1145/1806689.1806759MaRDI QIDQ2875178zbMATH OpenOpenAlexWikidataFDO

Authors Peter Bürgisser, Felipe Cucker

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

complexitypolynomial timepolynomial equation solvingsmoothed analysishomotopy methodsapproximate zero

Mathematics Subject Classification ID

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

Recommendations

• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• scientific article; zbMATH DE number 4106970
• Algorithms for near solutions to polynomial equations
• Smale 17th Problem: Advances and Open Directions
• Quasi-exact solvability in a general polynomial setting
• Polynomial-time solution of initial value problems using polynomial enclosures
• Solving systems of polynomial inequalities in subexponential time
• An improvement of the complexity bound for solving systems of polynomial equations
• Some remarks on Smale's “Algorithms for solving equations”
• Smooth polynomial solutions to a ternary additive equation

Cited in

(8)

• Fast computation of zeros of polynomial systems with bounded degree under finite-precision
• A faster solution to Smale's 17th problem. I: Real binomial systems
• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
• Smoothed analysis for the condition number of structured real polynomial systems
• On a problem posed by Steve Smale
• On Smale's 17th problem: a probabilistic positive solution
• A note on the finite variance of the averaging function for polynomial system solving
• Smale's 17th problem: average polynomial time to compute affine and projective solutions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875178)