A lower bound for randomized algebraic decision trees

DOI10.1007/BF01270387zbMath0895.68049MaRDI QIDQ1386178

Marek Karpinski, Roman Smolensky, Friedhelm Meyer auf der Heide, Dima Yu. Grigoriev

Publication date: 13 May 1998

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

knapsack problemelement distinctness problemrandomized algebraic decision trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Element distinctness revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
• Point location in arrangements of hyperplanes
• Lower bounds on probabilistic linear decision trees
• Solving systems of polynomial inequalities in subexponential time
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On randomized semi-algebraic test complexity
• Simulating probabilistic by deterministic algebraic computation trees
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Lower bounds for solving linear diophantine equations on random access machines
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• A Lower Bound to Finding Convex Hulls
• Lower bounds for algebraic decision trees
• Decision tree complexity and Betti numbers

This page was built for publication: A lower bound for randomized algebraic decision trees