A lower bound for randomized algebraic decision trees

DOI10.1007/BF01270387zbMATH Open0895.68049MaRDI QIDQ1386178FDOQ1386178

Authors: Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky, Dima Grigoriev 

Publication date: 13 May 1998

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

Recommendations

• scientific article; zbMATH DE number 1256781
• Randomization and the computational power of analytic and algebraic decision trees
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• scientific article; zbMATH DE number 1775407

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)

Cites Work

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

Cited In (10)

• Element distinctness revisited
• Lower bounds on probabilistic linear decision trees
• On randomized semi-algebraic test complexity
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Title not available (Why is that?)
• On the decisional complexity of problems over the reals

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

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