A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF

DOI10.1017/fms.2015.2zbMath1307.68037arXiv1403.6241OpenAlexW2963573218MaRDI QIDQ5177339

Felipe Cucker

Publication date: 11 March 2015

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.6241

Mathematics Subject Classification ID

Roundoff error (65G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78)

Related Items

Lower bounds for arithmetic networks. II: Sum of Betti numbers ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation ⋮ On the cost of iterative computations

Uses Software

• mctoolbox

Cites Work

• Unnamed Item
• Fast linear homotopy to find approximate zeros of polynomial systems
• Computability and complexity theory.
• On a problem posed by Steve Smale
• A numerical algorithm for zero counting. I: Complexity and accuracy
• Coverage processes on spheres and condition numbers for linear programming
• Exotic quantifiers, complexity classes, and complete problems
• On condition numbers and the distance to the nearest ill-posed problem
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Two \(P\)-complete problems in the theory of the reals
• It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
• Some perturbation theory for linear programming
• Computing over the reals with addition and order
• Complexity of Bezout's theorem. V: Polynomial time
• Computing over the reals with addition and order: Higher complexity classes
• Complexity of Bezout's theorem. III: Condition number and packing
• A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
• A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
• Condition
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• Complexity estimates depending on condition and round-off error
• Some Remarks on the Foundations of Numerical Analysis
• On the Complexity of Numerical Analysis
• Eigenvalues and Condition Numbers of Random Matrices
• The Relaxation Method for Solving Systems of Linear Inequalities
• Computational Complexity and Numerical Stability
• Sur la complexité du principe de Tarski-Seidenberg
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Paths, Trees, and Flowers
• Some Comments from a Numerical Analyst
• Numerical inverting of matrices of high order
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES
• Methods of conjugate gradients for solving linear systems
• Computational Complexity
• A new condition number for linear programming

This page was built for publication: A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF