Randomized vs. deterministic decision tree complexity for read-once Boolean functions

DOI10.1007/BF01212962zbMath0774.68061OpenAlexW2134298805MaRDI QIDQ685705

Rafi Heiman, Avi Wigderson

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01212962

zbMATH Keywords

read-once formulaeBoolean decision treesrandomized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Boolean functions (94D10)

Related Items (7)

Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Finding optimal satisficing strategies for and-or trees ⋮ Identification of partial disjunction, parity, and threshold functions ⋮ Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority ⋮ Query strategies for priced information ⋮ Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case ⋮ Complexity measures and decision tree complexity: a survey.

Cites Work

• Lower bounds on probabilistic linear decision trees
• On read-once threshold formulae and their randomized decision tree complexity
• Short monotone formulae for the majority function
• Optimal Search on Some Game Trees
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality
• Learning read-once formulas with queries

This page was built for publication: Randomized vs. deterministic decision tree complexity for read-once Boolean functions