Decision tree complexity and Betti numbers

DOI10.1006/jcss.1997.1495zbMath0880.68100OpenAlexW2764137104MaRDI QIDQ5906824

Andrew Chi-Chih Yao

Publication date: 28 October 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1495

zbMATH Keywords

algebraic computation tree

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (7)

Bounding the equivariant Betti numbers of symmetric semi-algebraic sets ⋮ Rough analysis of computation trees ⋮ Topological lower bounds for arithmetic networks ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ On topological lower bounds for algebraic computation trees ⋮ A complexity theory of constructible functions and sheaves ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Algebraic decision trees and Euler characteristics
• Lower bounds for arithmetic networks
• The homology of ``\(k\)-equal manifolds and related partition lattices
• Lower bounds on testing membership to a polyhedron by algebraic decision trees
• Lower bounds for algebraic decision trees
• On Parallel Computation for the Knapsack Problem
• Linear Decision Trees, Subspace Arrangements, and Mobius Functions
• 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

This page was built for publication: Decision tree complexity and Betti numbers