A lower bound for randomized algebraic decision trees
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 1256781 (Why is no real title available?)
- scientific article; zbMATH DE number 1256662 (Why is no real title available?)
- scientific article; zbMATH DE number 3345859 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- A Lower Bound to Finding Convex Hulls
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
- Decision tree complexity and Betti numbers
- Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
- Lower bounds for algebraic decision trees
- Lower bounds for solving linear diophantine equations on random access machines
- Lower bounds on probabilistic linear decision trees
- On randomized semi-algebraic test complexity
- Point location in arrangements of hyperplanes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Simulating probabilistic by deterministic algebraic computation trees
- Solving systems of polynomial inequalities in subexponential time
- The complexity of problems on probabilistic, nondeterministic, and alternating decision 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
- scientific article; zbMATH DE number 1559524 (Why is no real title available?)
- scientific article; zbMATH DE number 1390051 (Why is no real title available?)
- The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
- Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
- scientific article; zbMATH DE number 1256781 (Why is no real title available?)
- 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)
