Complexity measures and decision tree complexity: a survey

We discuss several complexity measures for Boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of Boolean functions on deterministic, randomized, and quantum computers.

Authors

• Harry Buhrman
• Ronald de Wolf

Keywords

• Decision tree complexity
• Complexity measures for Boolean functions
• Randomized computing
• Quantum computing