Topological lower bounds for arithmetic networks

DOI10.1007/s00037-016-0145-8zbMath1379.68150arXiv1510.03387OpenAlexW2405151523MaRDI QIDQ2410689

Nikolaj N. jun. Vorob'ev, Andrei Gabrielov

Publication date: 18 October 2017

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

semialgebraic setscomplexity lower boundsarithmetic networks

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)

Cites Work

• Unnamed Item
• Unnamed Item
• On topological lower bounds for algebraic computation trees
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• Lower bounds for arithmetic networks
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• 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: Topological lower bounds for arithmetic networks