Q The Query Complexity Zoo

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.