COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
From MaRDI portal
Publication:4344505
DOI10.1142/S0218127496001818zbMath0872.68036OpenAlexW1990400350WikidataQ57733293 ScholiaQ57733293MaRDI QIDQ4344505
Michael Shub, Felipe Cucker, Lenore Blum, Stephen Smale
Publication date: 17 July 1997
Published in: International Journal of Bifurcation and Chaos (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218127496001818
Related Items
Algorithms yield upper bounds in differential algebra, Random Points on an Algebraic Manifold, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, The Legacy of Turing in Numerical Analysis, Factoring multivariate polynomials via partial differential equations, Pseudozeros of multivariate polynomials, Time-Bounded Verification of CTMCs against Real-Time Specifications, Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries, Verification of Hybrid Systems, On the geometry of random lemniscates, Computability and Dynamical Systems, Interval Linear Algebra and Computational Complexity, Smoothing the Gap Between NP and ER, An Algebraic Proof of the Real Number PCP Theorem, Computation over algebraic structures and a classification of undecidable problems, Hausdorff approximations and volume of tubes of singular algebraic sets, Efficient simplicial replacement of semialgebraic sets, Two-step Newton's method for deflation-one singular zeros of analytic systems, Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Computing Semigroups with Error Control, The Condition Number of Join Decompositions, Bad Semidefinite Programs: They All Look the Same, On the expected number of real roots of polynomials and exponential sums, Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, On Σ‐definability without equality over the real numbers, Constraint Satisfaction Problems over Numeric Domains, Two conjectures on the arithmetic in ℝ and ℂ, Generalizing Computability Theory to Abstract Algebras, Minimizing the discrete logarithmic energy on the sphere: The role of random polynomials, CATEGORICAL COMPLEXITY, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Computability of String Functions Over Algebraic Structures Armin Hemmerling, An infinite family of bounds on zeros of analytic functions and relationship to Smale’s bound, Computability of Analytic Functions with Analytic Machines, On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants, There are significantly more nonnegative polynomials than sums of squares, The probability that a slightly perturbed numerical analysis problem is difficult, On the mathematical foundations of learning, Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods, Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer, Kantorovich's Theorem on Newton's Method for Solving Strongly Regular Generalized Equation, The Expected Number of Eigenvalues of a Real Gaussian Tensor, An Almost Optimal Algorithm for Computing Nonnegative Rank, Improved complexity results on solving real-number linear feasibility problems, Unnamed Item, Multihomogeneous Newton methods, Newton's method for overdetermined systems of equations, 96120 : The degree of the linear orbit of a cubic surface, Unnamed Item, A condition number theorem in convex programming, Unnamed Item, On the number of real roots of random polynomials, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, Feferman on Computability, Computability, noncomputability and undecidability of maximal intervals of IVPs, Non-computable Julia sets, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation, Computing a Nonnegative Matrix Factorization---Provably, Almost Transparent Short Proofs for NPℝ, The Complexity of the Nucleolus in Compact Games, In Praise of Numerical Computation, On the cost of iterative computations, Nonlinear Science — The Impact of Biology, The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs, Convergence of Newton’s method and inverse function theorem in Banach space, Counterexamples to the uniformity conjecture, The Condition Number of Riemannian Approximation Problems, Observations on Computability, Uncertainty, and Technology, 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, On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate, A Survey on Analog Models of Computation, Weihrauch Complexity in Computable Analysis, A short survey on Kantorovich, On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables, Epsilon local rigidity and numerical algebraic geometry, \textit{The critic as artist}: Oscar Wilde's prolegomena to shape grammars, Uniform convergence of higher order quasi Hermite-Fejér interpolation, Two-square theorems for infinite matrices on certain fields, Self-convexity and curvature, On the solution of the polynomial systems arising in the discretization of certain ODEs, Geometry and topology of proper polynomial mappings, Holant problems for 3-regular graphs with complex edge functions, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, Computing equilibria: a computational complexity perspective, Online calibrated forecasts: memory efficiency versus universality for learning in games, A primal-dual formulation for certifiable computations in Schubert calculus, Elimination of constants from machines over algebraically closed fields, Improved two-step Newton's method for computing simple multiple zeros of polynomial systems, Querying probabilistic business processes for sub-flows, Kantorovich's theorem on Newton's method under majorant condition in Riemannian manifolds, \(P\) versus \(NP\) and geometry, Dual VP classes, GPGCD: an iterative method for calculating approximate GCD of univariate polynomials, On the geometry and topology of the solution variety for polynomial system solving, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Smale's fundamental theorem of algebra reconsidered, Complexity of path-following methods for the eigenvalue problem, A continuation method to solve polynomial systems and its complexity, Harmonic properties of the logarithmic potential and the computability of elliptic Fekete points, Fast linear homotopy to find approximate zeros of polynomial systems, A framework for real-valued cipher systems, On Ladner's result for a class of real machines with restricted use of constants, On condition number theorems in mathematical programming, A geometric algorithm for winding number computation with complexity analysis, Computing with multiple discrete flows, Mapcode characterization of partial recursive maps, An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable, Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\), Small space analogues of Valiant's classes and the limitations of skew formulas, Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming, Effectiveness in RPL, with applications to continuous logic, A subdivision method for computing nearest gcd with certification, Extending the applicability of the Gauss-Newton method under average Lipschitz-type conditions, Robust certified numerical homotopy tracking, Energy of the Coulomb gas on the sphere at low temperature, On the expected number of zeros of nonlinear equations, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, A complex analogue of Toda's theorem, The computational complexity of evolutionarily stable strategies, Local and global behavior for algorithms of solving equations, Globally convergent, iterative path-following for algebraic equations, 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, The Turing degrees for some computation model with the real parameter, On a problem posed by Steve Smale, Extending the Kantorovich's theorem on Newton's method for solving strongly regular generalized equation, Computing the homology of real projective sets, Uncomputably large integral points on algebraic plane curves?, Analysis of a type of nonsmooth dynamical systems, Complexity classes and completeness in algebraic geometry, Tighter bounds of errors of numerical roots, Condition length and complexity for the solution of polynomial systems, Extended Newton-type method for nonlinear functions with values in a cone, Fixed points, Nash equilibria, and the existential theory of the reals, Grid methods in computational real algebraic (and semialgebraic) geometry, On cones of nonnegative quartic forms, The numerical factorization of polynomials, Second-level algorithms, superrecursivity, and recovery problem in distributed systems, Representation theorems for analytic machines and computability of analytic functions, On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers, On the intersection of a sparse curve and a low-degree curve: a polynomial version of the lost theorem, On the solution of systems of equations with constant rank derivatives, Probabilistic analysis of condition numbers for linear programming, On multivariate quantiles under partial orders, A note on the finite variance of the averaging function for polynomial system solving, On measures of space over real and complex numbers, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, Computing spectral measures and spectral types, Parametrised second-order complexity theory with applications to the study of interval computation, Real computational universality: the word problem for a class of groups with infinite presentation, Abstract geometrical computation. III: Black holes for classical and analog computing, Numerical elimination and moduli space of vacua, Correction to: ``Tropical varieties for exponential sums, A hierarchy below the halting problem for additive machines, From a zoo to a zoology: Towards a general theory of graph polynomials, Exotic quantifiers, complexity classes, and complete problems, Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric, Conditioning of random conic systems under a general family of input distributions, Random fields and the enumerative geometry of lines on real and complex hypersurfaces, Deformation techniques for sparse systems, Uncomputability and undecidability in economic theory, Interactive proofs and a Shamir-like result for real number computations, Counting problems over the reals, Computation by `While' programs on topological partial algebras, A facility location formulation for stable polynomials and elliptic Fekete points, A complexity theory of constructible functions and sheaves, Exact bivariate polynomial factorization over \(\mathbb Q\) by approximation of roots, Sensitivity of low-rank matrix recovery, On the computational structure of the connected components of a hard problem, Distribution of the eigenvalues of a random system of homogeneous polynomials, The PCP theorem for NP over the reals, P\(\neq\) NC over the \(p\)-adic numbers, A PCP of proximity for real algebraic polynomials, Some thoughts on computational models: from massive human computing to abstract state machines, and beyond, A dichotomy for real weighted Holant problems
