Smale's 17th problem: average polynomial time to compute affine and projective solutions
From MaRDI portal
(Redirected from Publication:3079201)
Recommendations
- On Smale's 17th problem: a probabilistic positive solution
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- On a problem posed by Steve Smale
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
Cites work
- A Fast Monte-Carlo Test for Primality
- A Note on Proper Maps
- A taxonomy of problems with fast parallel algorithms
- A universal constant for the convergence of Newton's method and an application to the classical homotopy method
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- Erratum: A Fast Monte-Carlo Test for Primality
- Estimates on the distribution of the condition number of singular matrices
- Estimations for the separation number of a polynomial system
- Fixed points, zeros and Newton's method
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- How to find all roots of complex polynomials by Newton's method.
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 5124810 (Why is no real title available?)
- scientific article; zbMATH DE number 1257074 (Why is no real title available?)
- scientific article; zbMATH DE number 503395 (Why is no real title available?)
- scientific article; zbMATH DE number 1859216 (Why is no real title available?)
- scientific article; zbMATH DE number 1418967 (Why is no real title available?)
- scientific article; zbMATH DE number 3280855 (Why is no real title available?)
- Newton's method and some complexity aspects of the zero-finding problem
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
- On Kolmogorov complexity in the real Turing machine setting
- On Smale's 17th problem: a probabilistic positive solution
- On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
- On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case
- Probabilistic algorithm for testing primality
- Riemann's hypothesis and tests for primality
- The best bounds in Gautschi's inequality
- TIME BOUNDED COMPUTATIONS OVER THE REALS
- Topological complexity of a root finding algorithm
Cited in
(48)- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- Complexity of Bezout's theorem. V: Polynomial time
- Random monomial ideals
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- On the geometry and topology of the solution variety for polynomial system solving
- Robust certified numerical homotopy tracking
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- Mixed precision path tracking for polynomial homotopy continuation
- A note on the finite variance of the averaging function for polynomial system solving
- Computing the homology of semialgebraic sets. I: Lax formulas
- A randomized homotopy for the Hermitian eigenpair problem
- An arithmetic Poisson formula for the multi-variate resultant
- Random sampling in computational algebra: Helly numbers and violator spaces
- Complexity of an homotopy method at the neighbourhood of a zero
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- The Legacy of Turing in Numerical Analysis
- Smale's polynomial problem
- Minimizing the discrete logarithmic energy on the sphere: the role of random polynomials
- On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant
- Smale's fundamental theorem of algebra reconsidered
- Complexity of path-following methods for the eigenvalue problem
- Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian
- A complex analogue of Toda's theorem
- scientific article; zbMATH DE number 1859208 (Why is no real title available?)
- What can we do with a solution?
- Smoothed analysis for the condition number of structured real polynomial systems
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- Condition length and complexity for the solution of polynomial systems
- A faster solution to Smale's 17th problem. I: Real binomial systems
- A theory of complexity, condition, and roundoff
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Some remarks on Smale's “Algorithms for solving equations”
- Numerical computation of the genus of an irreducible curve within an algebraic set
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- Probabilistic analyses of condition numbers
- Rigid continuation paths II. structured polynomial systems
- Learning a performance metric of Buchberger's algorithm
- Asymptotic degree of random monomial ideals
- A continuation method to solve polynomial systems and its complexity
- Fast linear homotopy to find approximate zeros of polynomial systems
- On a problem posed by Steve Smale
- The work of Steve Smale
- Optimal transport between algebraic hypersurfaces
- A Kronecker algorithm for locally closed sets over a perfect field
- On Smale's 17th problem: a probabilistic positive solution
This page was built for publication: Smale's 17th problem: average polynomial time to compute affine and projective solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3079201)
