Lower bounds on testing membership to a polyhedron by algebraic decision trees

DOI10.1145/195058.195418zbMath1345.68158OpenAlexW2080240172MaRDI QIDQ2817657

Marek Karpinski, Dima Yu. Grigoriev, Nikolaj N. jun. Vorob'ev

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.195418

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Complexity lower bounds for computation trees with elementary transcendental function gates ⋮ Semi-algebraic decision complexity, the real spectrum, and degree ⋮ A computationally intractable problem on simplicial complexes ⋮ Lower bound on testing membership to a polyhedron by algebraic decision and computation trees ⋮ Decision tree complexity and Betti numbers

This page was built for publication: Lower bounds on testing membership to a polyhedron by algebraic decision trees