Lower bounds on probabilistic linear decision trees
From MaRDI portal
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 Optimality of Some Set Algorithms
- On the Polyhedral Decision Problem
- On the complexity of computations under varying sets of primitives
- On the complexity of computing the measure of ∪[a i ,b i ]
Cited in
(30)- Decision trees: Old and new results.
- Applications of Ramsey's theorem to decision tree complexity
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- Decision trees with minimum average depth for sorting eight elements
- A randomized competitive algorithm for evaluating priced AND/OR trees
- Improved bounds for the randomized decision tree complexity of recursive majority
- Polynomial degree vs. quantum query complexity
- Randomized Boolean decision trees: Several remarks
- Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
- Separations between combinatorial measures for transitive functions
- The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
- Lower bounds on the length of universal traversal sequences
- scientific article; zbMATH DE number 1256781 (Why is no real title available?)
- Randomized query composition and sabotage complexity
- scientific article; zbMATH DE number 1700041 (Why is no real title available?)
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- scientific article; zbMATH DE number 3862434 (Why is no real title available?)
- Randomized versus deterministic decision tree size
- Randomized query composition and product distributions
- On the decisional complexity of problems over the reals
- Complexity measures and decision tree complexity: a survey.
- A New Lower Bound for the Set-Partitioning Problem
- Separation between deterministic and randomized query complexity
- On read-once threshold formulae and their randomized decision tree complexity
- Lower bounds to randomized algorithms for graph properties
- Approximate degree composition for recursive functions
- A lower bound for randomized algebraic decision trees
- Simulating probabilistic by deterministic algebraic computation trees
- scientific article; zbMATH DE number 3854414 (Why is no real title available?)
- Query strategies for priced information
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)
