Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
DOI10.1145/1806689.1806759zbMATH Open1293.68161OpenAlexW2076927517WikidataQ57733129 ScholiaQ57733129MaRDI QIDQ2875178FDOQ2875178
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
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
complexitypolynomial timepolynomial equation solvingsmoothed analysishomotopy methodsapproximate zero
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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)
