A composition theorem for decision tree complexity
From MaRDI portal
Recommendations
Cites work
- Complexity measures and decision tree complexity: a survey.
- On the degree of Boolean functions as real polynomials
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Reflections for quantum query algorithms
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
Cited in
(13)- On derandomized composition of Boolean functions
- Optimal direct sum results for deterministic and randomized decision tree complexity
- scientific article; zbMATH DE number 1285753 (Why is no real title available?)
- Complexity of Hierarchical Trees in Evidence Theory
- A composition theorem for randomized query complexity via max-conflict complexity
- A composition theorem for randomized query complexity
- Decision tree complexity and Betti numbers
- On (simple) decision tree rank
- The power of many samples in query complexity
- Randomized query composition and sabotage complexity
- Separations between combinatorial measures for transitive functions
- Randomized query composition and product distributions
- Lifting to randomized parity decision trees
This page was built for publication: A composition theorem for decision tree complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191149)
