Concepts
The prose that the tables lean on: conventions, why the settings differ, what composition is for, and the cheat sheets.
How to read this zoo
Conventions: what O(.) means here, what a 'witness' is, and how confident each entry is.
Total functions, partial functions, and relations
The single most important distinction in this zoo: almost every polynomial relation is a theorem about total Boolean functions only.
Cost conventions: worst case, expected cost, zero error
Why R_0 must be an expected-cost measure, and when worst-case and expected cost differ.
Dimensionless quantities and how to normalize them
MaxInf, NS and Stab are probabilities, not query counts. Why they cannot appear in the matrix, and what ratio to use instead.
Yao's minimax and its failures
The distributional characterisation of randomized query complexity: what is true, what Vereshchagin fixed, and where it breaks.
Composition
Does M(f o g) = M(f) M(g)? The answer distinguishes the well-behaved measures from the rest, and has spawned a family of measures of its own.
Direct sum and direct product
k independent copies of f: does it cost k times as much (direct sum), and does a smaller budget make you fail on almost all of them (direct product)?
Two different noisy query models
N_p (faulty oracle) and noisyR (bias purchasing) are NOT the same measure. Read this before using either.
The sensitivity conjecture (now Huang's theorem)
s, bs, C, deg, D are all polynomially related for total functions. Resolved in 2019; the exact exponents are still open.
Monotone functions
Everything collapses: s = bs = C, D <= s^2, and the quantum speedup is at most quadratic.
Cheat sheets: turning partial separations into total ones
The Aaronson-Ben-David-Kothari trick that converts a partial-function separation into a total-function separation with the same exponents.
Lifting: query complexity as a source of communication lower bounds
Why query-complexity measures are studied so intensely: composed with a small gadget, they transfer to communication complexity.
The adversary methods
From Ambainis' 2000 lower bound to the SDP that exactly characterises quantum query complexity.
Quantum sabotage: four variants
Separate the available oracle information from the requested output.
Operational certification complexity
Recognize a publicly known input against all opposite-output inputs, then maximize over the known input.