Semi-algebraic decision complexity, the real spectrum, and degree
From MaRDI portal
Publication:1916424
DOI10.1016/0022-4049(95)00105-0zbMath0853.68091OpenAlexW2077323669MaRDI QIDQ1916424
Publication date: 12 December 1996
Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-4049(95)00105-0
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10)
Related Items
Semi-algebraic complexity -- Additive complexity of matrix computational tasks, Semi-algebraic decision complexity, the real spectrum, and degree, How can a complex square root be computed in an optimal way?, Verification complexity of linear prime ideals, Some lower bounds for the complexity of the linear programming feasibility problem over the reals
Cites Work
- Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs
- Definability and fast quantifier elimination in algebraically closed fields
- Lectures on results on Bezout's theorem. Notes by D. P. Patil
- The complexity of evaluating interpolation polynomials
- The complexity of partial derivatives
- Test complexity of generic polynomials
- Verification complexity of linear prime ideals
- An elementary proof for Strassen's degree bound
- On randomized semi-algebraic test complexity
- Lower bounds for arithmetic networks
- Lower bounds for arithmetic networks. II: Sum of Betti numbers
- Semi-algebraic decision complexity, the real spectrum, and degree
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Berechnung und Programm. I
- Lower bounds on testing membership to a polyhedron by algebraic decision trees
- The Computational Complexity of Continued Fractions
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- On the real spectrum of a ring and its application to semialgebraic geometry
- An Extension of Strassen’s Degree Bound
- Lower bounds for algebraic decision trees
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Taylor expansion of the accumulated rounding error
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Heterogeneous algebras
- On the Betti Numbers of Real Varieties
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
