Lower bounds for algebraic decision trees

Cited In (35)

Decision trees: Old and new results.
Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs
New lower bounds for Hopcroft's problem
Subquadratic algorithms for algebraic 3SUM
Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
A variant of Ben-Or's lower bound for algebraic decision trees
A lower bound for the integer element distinctness problem
Time and space complexity of deterministic and nondeterministic decision trees
On selecting the k largest with median tests
Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
Algorithms for black-box fields and their application to cryptography
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
Better lower bounds on detecting affine and spherical degeneracies
An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
Local polyhedra and geometric graphs
On genuinely time bounded computations
Semi-algebraic decision complexity, the real spectrum, and degree
Some speed-ups and speed limits for real algebraic geometry
Rough analysis of computation trees
Unifying lower bounds for algebraic machines, semantically
On the complexity of the extreme points decision problem
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
Decision tree complexity and Betti numbers
On the topology of algorithms. I
Test complexity of generic polynomials
Nearly sharp complexity bounds for multiprocessor algebraic computations
On the decisional complexity of problems over the reals
Verification complexity of linear prime ideals
Some geometric lower bounds
PAC-learning in the presence of one-sided classification~noise
A lower bound for randomized algebraic decision trees
On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
Lower bounds for maximal and convex layers problems
Lower bounds for arithmetic networks. II: Sum of Betti numbers
Algebraic decision trees and Euler characteristics

This page was built for publication: Lower bounds for algebraic decision trees

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