Decision tree complexity and Betti numbers

DOI10.1145/195058.195414MaRDI QIDQ5890845zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195414

Mathematics Subject Classification ID

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

Recommendations

• Decision tree complexity and Betti numbers
• Decision trees: Old and new results.
• On topological lower bounds for algebraic computation trees
• Algebraic decision trees and Euler characteristics
• scientific article; zbMATH DE number 1256662

Cited in

(23)

• Nearly sharp complexity bounds for multiprocessor algebraic computations
• Complexity lower bounds for computation trees with elementary transcendental function gates
• A lower bound for randomized algebraic decision trees
• Randomization and the computational power of analytic and algebraic decision trees
• Computational topology: Ambient isotopic approximation of 2-manifolds.
• A computationally intractable problem on simplicial complexes
• Time and space complexity of deterministic and nondeterministic decision trees
• On decision trees for orthants
• scientific article; zbMATH DE number 5373718 (Why is no real title available?)
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• scientific article; zbMATH DE number 1256662 (Why is no real title available?)
• scientific article; zbMATH DE number 1285753 (Why is no real title available?)
• Complexity of Hierarchical Trees in Evidence Theory
• Lower bounds on algebraic random access machines
• A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma
• On the computational complexity of Betti numbers: reductions from matrix rank
• Transactions on Rough Sets III
• scientific article; zbMATH DE number 7651142 (Why is no real title available?)
• scientific article; zbMATH DE number 7650404 (Why is no real title available?)
• Decision tree complexity and Betti numbers
• The complexity of bicriteria tree-depth
• Algebraic decision trees and Euler characteristics
• Lower bound on testing membership to a polyhedron by algebraic decision and computation trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890845)