- Decision Tree Complexity (deterministic query complexity)
- Certificate Complexity
- Block Sensitivity
- Degree of approximate polynomial
- Degree of exact polynomial
- Quantum query complexity
Links:
- Quantum lower bounds by polynomials by Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf
- On the degree of boolean functions as real polynomials by Noam Nisan and Mario Szegedy
