Lower bounds on probabilistic linear decision trees
From MaRDI portal
Probabilistic linear one sided decision trees are examined. A technique is developed to derive lower bounds for the average number of comparisons in such trees from lower bounds on deterministic trees. Using it, \(\Omega\) (n lg n) lower bounds are derived for problems such as element uniqueness, set equality, etc. Standard lower bound arguments for deterministic decision trees are shown to be valid for probabilistic decision trees. Nevertheless, a simple problem is described where use of random choices provably saves time.
Recommendations
- Lower bounds for linear decision trees with bounded weights
- Lower bounds for linear decision trees via an energy complexity argument
- scientific article; zbMATH DE number 3858831
- Lower bounds on learning decision lists and trees
- Lower bounds on learning decision lists and trees
- scientific article; zbMATH DE number 1179978
- A lower bound for randomized algebraic decision trees
- scientific article; zbMATH DE number 1256781
- Lower bounds for external algebraic decision trees
- scientific article; zbMATH DE number 927106
Cites work
- scientific article; zbMATH DE number 3738914 (Why is no real title available?)
- On Finding the Maxima of a Set of Vectors
- On the complexity of computations under varying sets of primitives
- On the complexity of computing the measure of ∪[a i ,b i ]
- On the Optimality of Some Set Algorithms
- On the Polyhedral Decision Problem
Cited in
(30)- Lower bounds on the length of universal traversal sequences
- On read-once threshold formulae and their randomized decision tree complexity
- Randomized Boolean decision trees: Several remarks
- A lower bound for randomized algebraic decision trees
- Simulating probabilistic by deterministic algebraic computation trees
- Complexity measures and decision tree complexity: a survey.
- Decision trees: Old and new results.
- On the decisional complexity of problems over the reals
- Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
- Polynomial degree vs. quantum query complexity
- Decision trees with minimum average depth for sorting eight elements
- scientific article; zbMATH DE number 1700041 (Why is no real title available?)
- Improved bounds for the randomized decision tree complexity of recursive majority
- scientific article; zbMATH DE number 3854414 (Why is no real title available?)
- scientific article; zbMATH DE number 3862434 (Why is no real title available?)
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
- Applications of Ramsey's theorem to decision tree complexity
- A New Lower Bound for the Set-Partitioning Problem
- scientific article; zbMATH DE number 1256781 (Why is no real title available?)
- Separation between deterministic and randomized query complexity
- Randomized versus deterministic decision tree size
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- Randomized query composition and sabotage complexity
- Separations between combinatorial measures for transitive functions
- Randomized query composition and product distributions
- Approximate degree composition for recursive functions
- Query strategies for priced information
- Lower bounds to randomized algorithms for graph properties
- A randomized competitive algorithm for evaluating priced AND/OR trees
This page was built for publication: Lower bounds on probabilistic linear decision trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1067786)
