Randomized vs. deterministic decision tree complexity for read-once Boolean functions
From MaRDI portal
Publication:685705
DOI10.1007/BF01212962zbMATH Open0774.68061OpenAlexW2134298805MaRDI QIDQ685705FDOQ685705
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
Recommendations
- Bounding the randomized decision tree complexity of read-once Boolean functions
- Randomized Boolean decision trees: Several remarks
- Lower bounds on the randomized communication complexity of read-once functions
- On directional vs. general randomized decision tree complexity for read-once formulas
- The Computational Complexity of Game Trees by Eigen-Distribution
Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Boolean functions (94D10)
Cites Work
- Learning read-once formulas with queries
- 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
- On read-once threshold formulae and their randomized decision tree complexity
- Lower bounds on probabilistic linear decision trees
Cited In (8)
- Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
- Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
- Finding optimal satisficing strategies for and-or trees
- Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
- Complexity measures and decision tree complexity: a survey.
- On read-once threshold formulae and their randomized decision tree complexity
- Identification of partial disjunction, parity, and threshold functions
- Query strategies for priced information
This page was built for publication: Randomized vs. deterministic decision tree complexity for read-once Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685705)
