Lower bounds on probabilistic linear decision trees

DOI10.1016/0304-3975(85)90210-5zbMATH Open0581.68042OpenAlexW2026325622MaRDI QIDQ1067786FDOQ1067786

Authors: Marc Snir 

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90210-5

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
• Publication:4892375

zbMATH Keywords

probabilistic algorithmsset equalityrandom choiceselement uniquenessprobabilistic decision trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Cites Work

• On Finding the Maxima of a Set of Vectors
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• On the complexity of computations under varying sets of primitives
• On the Polyhedral Decision Problem
• On the Optimality of Some Set Algorithms
• Title not available (Why is that?)

Cited In (26)

• Applications of Ramsey's theorem to decision tree complexity
• Decision trees: Old and new results.
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Decision trees with minimum average depth for sorting eight elements
• Improved bounds for the randomized decision tree complexity of recursive majority
• A randomized competitive algorithm for evaluating priced AND/OR trees
• Polynomial degree vs. quantum query complexity
• Randomized Boolean decision trees: Several remarks
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Lower bounds on the length of universal traversal sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• Randomized versus deterministic decision tree size
• Title not available (Why is that?)
• On the decisional complexity of problems over the reals
• A New Lower Bound for the Set-Partitioning Problem
• Complexity measures and decision tree complexity: a survey.
• 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
• A lower bound for randomized algebraic decision trees
• Simulating probabilistic by deterministic algebraic computation trees
• Title not available (Why is that?)
• 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)