Decision tree complexity and Betti numbers
From MaRDI portal
Publication:5890845
DOI10.1145/195058.195414zbMath1345.68297OpenAlexW2068645950MaRDI QIDQ5890845
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
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 (12)
On decision trees for orthants ⋮ Nearly sharp complexity bounds for multiprocessor algebraic computations ⋮ Complexity lower bounds for computation trees with elementary transcendental function gates ⋮ A computationally intractable problem on simplicial complexes ⋮ A lower bound for randomized algebraic decision trees ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Unnamed Item ⋮ Computational topology: Ambient isotopic approximation of 2-manifolds. ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Lower bound on testing membership to a polyhedron by algebraic decision and computation trees ⋮ Lower bounds on algebraic random access machines
This page was built for publication: Decision tree complexity and Betti numbers
