Lower bounds on probabilistic linear decision trees

DOI10.1016/0304-3975(85)90210-5zbMath0581.68042OpenAlexW2026325622MaRDI QIDQ1067786

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

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)

Related Items (17)

Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ A lower bound for randomized algebraic decision trees ⋮ Separation Between Deterministic and Randomized Query Complexity ⋮ A randomized competitive algorithm for evaluating priced AND/OR trees ⋮ Randomized vs. deterministic decision tree complexity for read-once Boolean functions ⋮ Lower bounds on the length of universal traversal sequences ⋮ On read-once threshold formulae and their randomized decision tree complexity ⋮ Query strategies for priced information ⋮ Polynomial degree vs. quantum query complexity ⋮ Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case ⋮ Improved bounds for the randomized decision tree Complexity of recursive majority ⋮ Randomized Boolean decision trees: Several remarks ⋮ 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 ⋮ Lower bounds to randomized algorithms for graph properties

Cites Work

• Unnamed Item
• On the complexity of computations under varying sets of primitives
• On the Polyhedral Decision Problem
• On Finding the Maxima of a Set of Vectors
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• On the Optimality of Some Set Algorithms

This page was built for publication: Lower bounds on probabilistic linear decision trees