Smale's 17th problem: average polynomial time to compute affine and projective solutions
From MaRDI portal
Publication:3079201
DOI10.1090/S0894-0347-08-00630-9zbMATH Open1206.90173WikidataQ56697970 ScholiaQ56697970MaRDI QIDQ3079201FDOQ3079201
Luis Miguel Pardo, Carlos Beltran
Publication date: 2 March 2011
Published in: Journal of the American Mathematical Society (Search for Journal in Brave)
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
Nonlinear programming (90C30) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)
Cites Work
- Title not available (Why is that?)
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On a theory of computation and complexity over the real numbers: đđ- completeness, recursive functions and universal machines
- Title not available (Why is that?)
- A taxonomy of problems with fast parallel algorithms
- Fixed points, zeros and Newton's method
- Probabilistic algorithm for testing primality
- Riemann's hypothesis and tests for primality
- The best bounds in Gautschi's inequality
- A Fast Monte-Carlo Test for Primality
- On Smale's 17th problem: a probabilistic positive solution
- Complexity of Bezoutâs Theorem IV: Probability of Success; Extensions
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- On Kolmogorov complexity in the real Turing machine setting
- A Note on Proper Maps
- Topological complexity of a root finding algorithm
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's Theorem I: Geometric Aspects
- Estimates on the distribution of the condition number of singular matrices
- Title not available (Why is that?)
- On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
- Title not available (Why is that?)
- How to find all roots of complex polynomials by Newton's method.
- Title not available (Why is that?)
- Title not available (Why is that?)
- On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
- Erratum: A Fast Monte-Carlo Test for Primality
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- 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
- Estimations for the separation number of a polynomial system
- Title not available (Why is that?)
- A universal constant for the convergence of Newton's method and an application to the classical homotopy method
- TIME BOUNDED COMPUTATIONS OVER THE REALS
- Newton's method and some complexity aspects of the zero-finding problem
Cited In (41)
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- Smale's fundamental theorem of algebra reconsidered
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- A continuation method to solve polynomial systems and its complexity
- The Legacy of Turing in Numerical Analysis
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Minimizing the discrete logarithmic energy on the sphere: The role of random polynomials
- Smoothed analysis for the condition number of structured real polynomial systems
- Random sampling in computational algebra: Helly numbers and violator spaces
- Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian
- Random monomial ideals
- On a problem posed by Steve Smale
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- Title not available (Why is that?)
- Asymptotic degree of random monomial ideals
- On Smale's 17th problem: a probabilistic positive solution
- A complex analogue of Toda's theorem
- On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- A note on the finite variance of the averaging function for polynomial system solving
- A promenade through correct test sequences. I: Degree of constructible sets, BĂ©zout's inequality and density
- Fast linear homotopy to find approximate zeros of polynomial systems
- Complexity of path-following methods for the eigenvalue problem
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Probabilistic analyses of condition numbers
- On the geometry and topology of the solution variety for polynomial system solving
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of an Homotopy Method at the Neighbourhood of a Zero
- Computing the homology of semialgebraic sets. I: Lax formulas
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- Rigid continuation paths II. structured polynomial systems
- Condition length and complexity for the solution of polynomial systems
- Mixed precision path tracking for polynomial homotopy continuation
- A randomized homotopy for the Hermitian eigenpair problem
- Learning a performance metric of Buchberger's algorithm
- Robust certified numerical homotopy tracking
- An arithmetic Poisson formula for the multi-variate resultant
- A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
- Numerical computation of the genus of an irreducible curve within an algebraic set
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)
