Randomized vs. deterministic decision tree complexity for read-once Boolean functions
From MaRDI portal
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
Cites work
- Learning read-once formulas with queries
- Lower bounds on probabilistic linear decision trees
- On read-once threshold formulae and their randomized decision tree complexity
- Optimal Search on Some Game Trees
- Short monotone formulae for the majority function
- The solution for the branching factor of the alpha-beta pruning algorithm and its optimality
Cited in
(11)- Bounding the randomized decision tree complexity of read-once Boolean functions
- Identification of partial disjunction, parity, and threshold functions
- Finding optimal satisficing strategies for and-or trees
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
- Complexity measures and decision tree complexity: a survey.
- Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
- On directional vs. general randomized decision tree complexity for read-once formulas
- An improved lower bound for the randomized decision tree complexity of recursive majority
- On read-once threshold formulae and their randomized decision tree complexity
- 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)
