On topological lower bounds for algebraic computation trees

DOI10.1007/s10208-015-9283-7zbMath1365.14080arXiv1502.04341OpenAlexW2963960422MaRDI QIDQ525599

Andrei Gabrielov, Nikolaj N. jun. Vorob'ev

Publication date: 5 May 2017

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

semialgebraic setsalgebraic computation treescomplexity lower bounds

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Topology of real algebraic varieties (14P25)

Related Items (4)

Rough analysis of computation trees ⋮ Topological lower bounds for arithmetic networks ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Topological perplexity of feedback stabilization

Cites Work

• Unnamed Item
• On the complexity of computations under varying sets of primitives
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• Decision tree complexity and Betti numbers

This page was built for publication: On topological lower bounds for algebraic computation trees