Lower bounds for algebraic decision trees
From MaRDI portal
Publication:3933758
DOI10.1016/0196-6774(82)90002-5zbMath0477.68065OpenAlexW2044850435MaRDI QIDQ3933758
J. Michael Steele, Andrew Chi-Chih Yao
Publication date: 1982
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(82)90002-5
knapsack problemconvex hull problemdistinct element problemlower bounds for the height of algebraic decision trees
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\), Algorithms for Black-Box Fields and their Application to Cryptography, Better lower bounds on detecting affine and spherical degeneracies, A variant of Ben-Or's lower bound for algebraic decision trees, On the topology of algorithms. I, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers, Nearly sharp complexity bounds for multiprocessor algebraic computations, Lower bounds for arithmetic networks. II: Sum of Betti numbers, On selecting the k largest with median tests, Semi-algebraic decision complexity, the real spectrum, and degree, Rough analysis of computation trees, A lower bound for randomized algebraic decision trees, On genuinely time bounded computations, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Subquadratic algorithms for algebraic 3SUM, Time and space complexity of deterministic and nondeterministic decision trees, A lower bound for the integer element distinctness problem, On the complexity of the extreme points decision problem, On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Algebraic decision trees and Euler characteristics, Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs, Test complexity of generic polynomials, PAC-learning in the presence of one-sided classification~noise, Verification complexity of linear prime ideals, Decision tree complexity and Betti numbers, Local polyhedra and geometric graphs, New lower bounds for Hopcroft's problem, Lower bounds for maximal and convex layers problems, On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, Decision trees: Old and new results., On the decisional complexity of problems over the reals, Some speed-ups and speed limits for real algebraic geometry, An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
