Q The Query Complexity Zoo

Functions

The witnesses. Every separation in the zoo points at one of these families; every page gives the definition (or says plainly that it has not been transcribed yet), the measure values that make it interesting, and the separations it witnesses.

Total functions

f : {0,1}^n -> {0,1} defined on the whole cube. Where all measures are polynomially related.

SymbolNameGroupDefinition given?Why it matters
\(\mathrm{OR}_n\) OR
OR
basic The archetypal one-sided function: cheap 1-certificates, expensive 0-certificates.
\(\mathrm{AND}_n\) AND
AND
basic The dual of OR; the witness cited in most "$2,2$" and "$2,4$" cells of the total-function matrix.
\(\oplus_n\) PARITY
PARITY
basic Maximally hard for every measure in the zoo except parity decision trees -- hence the witness for every "$1,1$" cell.
\(\mathrm{MAJ}_n\) MAJORITY
MAJ
basic Hard for quantum too ($\mathrm{Q}=\Theta(n)$), but with sensitivity only $\approx n/2$.
\(\mathrm{THR}^n_k\) Threshold
THR
basic The whole one-parameter family interpolating OR ($k=1$), MAJ ($k=n/2$) and AND ($k=n$).
\(f = f(|x|)\) Symmetric functions (general)
SYM
basic Every measure in the polynomial/quantum column is pinned down exactly by Paturi's theorem.
\(\mathrm{EH}_n\) EXACT-HALF
EH
basic Nondeterministic degree 1 for the negation -- the engine behind the rdeg separations.
\(\mathrm{OMB}_n\) ODD-MAX-BIT
OMB
basic Sign degree $1$, deterministic complexity $n$: the extreme sdeg separation.
\(\mathrm{ADDR}_k\) ADDRESS / multiplexer
ADDR
basic The standard gadget in lifting theorems and in "adaptivity is necessary" arguments.
\(\mathrm{Nav}_k\) Binary tree navigation
TreeNav
basic Adaptivity at its most extreme: $\mathrm{D}=k$ but every one of the $2^k-1$ variables is relevant.
\(\mathrm{Tribes}_{w,s}\) TRIBES
TRIBES
basic Balanced read-once DNF; the KKL / max-influence extremal example.
\(\mathrm{IP}_n\) Inner product mod 2
IP
basic Everything combinatorial is $n$ and everything Fourier is as spread out as it can be: the flat spectrum makes $\mathrm{L}_1 = 2^{n/2}$ with $\mathrm{spar} = 2^n$.
\(\mathrm{SCORP}_m\) Scorpion graphs
SCORPION
basic The nontrivial graph property that is nowhere near evasive: $\mathrm{D} = \Theta(m) = \Theta(\sqrt N)$ out of $N$ possible queries.
\(\mathrm{CONN}_m\) Graph connectivity
CONN
basic The monotone graph property everyone checks first: evasive, $\mathrm{R} = \Theta(N)$, and $\mathrm{Q} = \Theta(N^{3/4})$.
\(\mathrm{AND}_n \circ \mathrm{OR}_n\) AND-OR tree (depth 2)
ANDOR
composed $\mathrm{D}=\mathrm{R}=\Theta(N)$ while $\mathrm{C}=\mathrm{bs}=\sqrt N$; also separates sabotage and max-conflict from conflict complexity.
\(\bar{\wedge}\text{-tree}\) NAND tree (balanced AND-OR formula)
NANDtree
composed The Saks-Wigderson function: $\mathrm{R}_0 = \Theta(N^{0.7537})$, $\mathrm{Q}=\Theta(\sqrt N)$, $\deg = N$.
\(\mathrm{MAJ}_3^{\circ d}\) Recursive MAJORITY-of-3
RMAJ3
composed The other classical recursive benchmark; its randomized complexity is still not pinned down.
\(K^{\circ k}\) Kushilevitz's function (iterated)
Kushilevitz
composed A 6-variable function with $\deg = 3$ and $\mathrm{s}=6$; iterating gives $\mathrm{s} = \deg^{1.63}$.
\(f_{\mathrm{Rub}}\) Rubinstein's function
Rubinstein
composed The classical quadratic separation $\mathrm{bs} = \tfrac12\mathrm{s}^2$.
\(f_{\mathrm{AS}}\) Ambainis-Sun function
AmbainisSunFn
composed Improves Rubinstein's constant to $\mathrm{bs} = \tfrac23 \mathrm{s}^2 - \tfrac13 \mathrm{s}$.
\(\mathrm{AND}_n \circ \overline{\mathrm{EH}}_n\) AND composed with NOT-EXACT-HALF
ANDEH
composed The witness for the whole rdeg column: $\mathrm{rdeg}=\Theta(n)$ while $\mathrm{s},\deg,\mathrm{D}=\Theta(n^2)$.
\(f_{\mathrm{Mei}}\) Meiburg's tournament-subcube function
MeiburgTournament
composed Refutes $\mathrm{bs} = O(\lambda^2)$: a total function with $\mathrm{bs} \ge \lambda^{2.127}$.
\(\mathrm{MP}_m\) Minsky-Papert one-in-a-box
MinskyPapert
composed The unbalanced AND-OR tree, tuned so that Minsky-Papert's $\min\{m,\sqrt b\}$ is maximised: $\mathrm{sdeg} = \Theta(N^{1/3})$.
\(P_q\) Meiburg’s parity-pointer family
MeiburgParityPointer
composed A total logarithmic separation of sabotage from conflict, max-conflict, linearised and randomized query complexity.
\(M_q\) Meiburg’s majority-pointer family
MeiburgMajorityPointer
composed A total logarithmic separation of randomized from linearised query complexity.
\(G_q\) Meiburg’s parity-masked majority family
MeiburgMaskedPointer
composed A total square-root-logarithmic separation of linearised from max-conflict complexity.
\(W_q\) Meiburg’s total noisy-query separation
MeiburgNoisySeparation
composed Total functions with $\mathrm{R}/\mathrm{noisyR}=\Omega((\log N)^{1/4}/\log\log\log N)$.
\(H_q\) Meiburg’s maximal composition-rate separation
MeiburgCompositionRate
composed $\mathrm{R}^{*}/\mathrm{R}=\Theta(\log\mathrm{R})$, the maximal logarithmic gap.
\(F_{k,m}\) OpenAI’s nearly quartic randomized–quantum family
OpenAIQuarticRQ
composed Settles the optimal total-function $\mathrm{R}$-versus-$\mathrm{Q}$ exponent at $4$.
\(\overline f_{\mathrm{AIK}}\) Complement of the Ambainis–Iraids–Kokainis DNF
AIKDNFComplement
composed Logarithm-free quadratic $\mathrm{C}$ versus certain-acceptance one-sided $\mathrm{R}^1$ separation.
\(\mathrm{ED}_n\) Element distinctness
ElementDistinctness
quantum $\mathrm{Q}=\Theta(n^{2/3})$ vs $\mathrm{R}=\Theta(n)$; a total (non-Boolean-input) function.
\(\mathrm{SURJ}_{N,R}\) Surjectivity
Surjectivity
quantum The only known natural function separating $\mathrm{Q}$ from $\widetilde{\deg}$: $\widetilde{\deg} = \tilde\Theta(n^{3/4})$ while $\mathrm{Q} = \tilde\Theta(n)$.
\(\mathrm{DIST}^k_n\) $k$-distinctness
KDistinctness
quantum $\mathrm{Q} = \Theta(n^{3/4 - 1/(4(2^k-1))})$, settled in 2026 after fourteen years; the approximate degree is still open.
\(\mathrm{TRI}_m\) Triangle finding
TriangleFinding
quantum The flagship open problem of quantum query complexity: $\Omega(m)$ against $O(m^{5/4})$, stuck for twenty years.
\(g_{\mathrm{ABBLSS}}\) Pointer functions
pointer
separating The construction that refuted the Saks-Wigderson conjecture and set most of the top-left corner of the matrix.
\(f_{\mathrm{CS}}\) Cheat-sheet functions
cheatsheet
separating A generic transformation turning a partial-function separation into a total-function separation.
\(f_{\mathrm{BHT}}\) Low-sensitivity function from unambiguous certificates
BHTfn
separating The current record for D-vs-s: $\mathrm{D} = \widetilde\Omega(\mathrm{s}^3)$.
\(f_{\mathrm{BBGJK}}\) Unambiguous-DNF / Alon-Saks-Seymour function
BBGJKfn
separating Sets the C row: $\mathrm{C}=\widetilde\Omega(\mathrm{s}^3)$, $\widetilde\Omega(\lambda^4)$, $\widetilde\Omega(\deg^2)$, $\widetilde\Omega(\widetilde{\deg}^3)$.
\(f_{\mathrm{GSS}}\) Gilmer-Saks-Srinivasan functions
GSSfn
separating Separates C from RC quadratically -- with no log loss -- and RC from bs by a $3/2$ power.
\(g_n\) Random-indicator gadget
GSSinner
separating The inner gadget of \(f_{\mathrm{GSS}}\), on its own: $\mathrm{C}^0 = \Theta(n)$ with $\mathrm{bs}^0 = O(1)$.
\(f_{\mathrm{GPW}}\) Goos-Pitassi-Watson partition-number function
GPWfn
separating The query-side function behind "deterministic communication vs partition number"; gives $\mathrm{D}=\widetilde\Omega(\deg^2)$.
\(f_{\mathrm{GJPW}}\) Goos-Jayram-Pitassi-Watson function
GJPWfn
separating Randomized analogue of GPW: $\mathrm{R}_0, \mathrm{R} = \widetilde\Omega(\deg^2)$.
\(\mathrm{NE}^d\) Ambainis' exact-quantum function
Ambainis13fn
separating The first total function with a superlinear exact quantum speedup: $\mathrm{Q}_E = O(\mathrm{D}^{0.8675})$.
\(\mathrm{SINK}_m\) Sink of a tournament
SINK
separating The function that killed the log-approximate-rank conjecture: spectral norm $O(\sqrt N)$, but $\mathrm{SINK}\circ\mathrm{XOR}$ has randomized communication complexity $\Omega(\sqrt N)$.
Champion Ben-David–Kothari championship function
Champion
separating-total Simultaneously $\mathrm{C}=\Omega(n^2)$, $\mathrm{R}=O(n\log n)$ and $\mathrm{Q}=\widetilde O(\sqrt n)$.
\(\mathrm{AIKuD}\) Ambainis–Iraids–Kokainis unambiguous DNF
AIKDNF
separating-total Log-free optimal separation $\mathrm{C}=\Theta(\mathrm{R}_{\mathrm{RP}}^2)$.
\(\mathrm{AIKCS}\) Ambainis–Iraids–Kokainis certificate cheat sheet
AIKCheatSheet
separating-total Quartic $\mathrm{C}/\mathrm{Q}$ and $\mathrm{R}_0/\mathrm{Q}$ separations, with quadratic $\mathrm{C}/\mathrm{Q}_{\mathrm{E}}$ and $\mathrm{C}/\mathrm{Q}_0$.
PabbarajuDNF Pabbaraju’s optimal unambiguous DNF
PabbarajuDNF
separating-total $\mathrm{C}^0=\Omega(n^2)$ and $\mathrm{UC}^1=O(n)$, without logarithmic losses.
PabbarajuQuartic Pabbaraju’s quartic approximate-degree function
PabbarajuQuartic
separating-total $\mathrm{C}\ge\Omega(\widetilde{\deg}^{\,4}/\log^6 n)$; settles the exponent at four.
\(\mathrm{PabCS}\) Pabbaraju’s certificate–sensitivity separator
PabbarajuCubicSensitivity
separating-total Log-free $\mathrm{C}=\Omega(\mathrm{s}^3)$.
OpenAINestedTournament OpenAI’s nested tournament sensitivity separator
OpenAINestedTournament
separating-total Refutes $\mathrm{bs}=O(\mathrm{s}^2)$; a fixed seed yields an exponent strictly greater than two.
Prove2MeTournament Prove2Me’s refined tournament sensitivity family
Prove2MeTournament
separating-total $\mathrm{bs}\ge\mathrm{s}^{\alpha-o(1)}$, $\alpha=\log(14055^8)/\log(3738277295413674)=2.1308255793978239\ldots$.
ANDNotExactOne AND of complemented EXACT-ONE functions
ANDNotExactOne
separating-total New quantum-certification lower bounds separate $\mathrm{Q}_0$ from both $\mathrm{Q}$ and rational degree.

Partial functions

f : Dom(f) -> {0,1} with Dom(f) a proper subset of the cube (promise problems). Most polynomial relations FAIL here.

SymbolNameGroupDefinition given?Why it matters
\(\mathrm{forr}\) FORRELATION
Forrelation
quantum One quantum query vs $\widetilde\Theta(\sqrt n)$ randomized queries -- the maximal possible gap at $\mathrm{Q}=1$.
\(\mathrm{forr}_k\) k-FORRELATION
kForrelation
quantum Optimal $\mathrm{Q}$-vs-$\mathrm{R}$ separation for every $k$: $\mathrm{Q}=\lceil k/2\rceil$, $\mathrm{R}=\widetilde\Theta(n^{1-1/k})$.
\(\mathrm{SIMON}_n\) Simon's problem
Simon
quantum The first exponential quantum speedup for a promise problem: $\mathrm{Q}=O(n)$ vs $\mathrm{R}=\Omega(2^{n/2})$.
\(\mathrm{DJ}_n\) Deutsch-Jozsa
DeutschJozsa
quantum Exact quantum: 1 query vs $N/2+1$ deterministic queries (but $\mathrm{R}=O(1)$).
\(\mathrm{BV}_n\) Bernstein-Vazirani
BV
quantum One exact quantum query recovers an $n$-bit secret that costs $n$ classical queries.
\(\mathrm{SEARCH}^{\le 1}_n\) Unique search
UniqueSearch
quantum Grover search as a partial function. The reason it is in the zoo: $\deg = 1$ while $\widetilde{\deg} = \Theta(\sqrt n)$, so $\widetilde{\deg} \le \deg$ -- a triviality for total functions -- fails outright on a promise.
\(\mathrm{SEARCH}^{0/2}_n\) Two-or-none search
Search02
quantum \(\mathrm{SEARCH}^{\le 1}_n\) with the promise moved from $|x|\le 1$ to $|x|\in\{0,2\}$. No two domain points are now adjacent, so $\mathrm{s} = \lambda = 0$, while $\mathrm{Q} = \mathrm{Adv} = \Theta(\sqrt n)$ is untouched.
\(\mathrm{MARK}_n\) Marked bit
MarkedBit
quantum The certificate barrier at full strength: $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = 1$, yet $\widetilde{\deg} = \mathrm{Q} = \Theta(\sqrt n)$ and $\mathrm{R} = \mathrm{D} = \Theta(n)$. Recognising the answer is one query; finding it is Grover.
\(\mathrm{DMARK}_n\) Dense marked bit
DenseMarkedBit
quantum Zero-error randomized cost $O(1)$ against $\deg = \mathrm{Q}_E = \Theta(n)$: the cheapest witness that exact degree is not bounded by any function of $\mathrm{R}_0$ off the promise.
\(\mathrm{COL}_n\) Collision problem
Collision
quantum $\mathrm{Q}=\Theta(n^{1/3})$ vs $\mathrm{R}=\Theta(\sqrt n)$: a polynomial-only quantum speedup for a promise problem.
\(\mathrm{TSAT}_n\) Ambainis-Belovs function
AmbainisBelovsFn
quantum Constant exact degree ($\le 9$) against $\mathrm{Q} = \Omega(n^{1/3})$: the polynomial method is exponentially lossy off-promise.
\(\mathrm{RFS}^g_\ell\) Recursive Fourier sampling
RecursiveFourierSampling
quantum The original superpolynomial oracle separation: $\mathrm{Q}_E = 2^\ell$ against $n^{\Omega(\log n)}$ classically at $\ell = \log n$.
\(\mathrm{GapMaj}^{\delta}_{n}\) Gap-Majority
GapMaj
separating The universal "hardest easy" promise problem; characterises noisy randomized complexity.
\(\mathrm{GapMaj}^{1/4}_{n}\) Gap-Majority at constant gap
GapMajConst
separating The $\delta = 1/4$ instance of Gap-Majority: $\Theta(1)$ for every bounded-error measure, $\Theta(n)$ for every exact one.
\(\mathrm{Find1}^{\mathrm{par}}_{n}\) Parity-labelled FIND-1
Find1Parity
separating The decision version of FIND-1: zero-error $O(1)$ against deterministic $n/4+1$.
\(\mathrm{ApproxIndex}_k\) Approximate index
ApproxIndex
separating The outer function that refutes the randomized composition conjecture: a biased guess at the index is good enough, which is cheap noisily and expensive classically.
\(\mathrm{OS}_n\) Ordered search
OrderedSearch
separating Where quantum buys only a constant factor: $\mathrm{D} = \lceil\log_2(n+1)\rceil$ and $\mathrm{Q} = \Theta(\log n)$, with the constant pinned between $0.221$ and $0.390$.

Relations

f subset of {0,1}^n x O : any output o with (x,o) in f is acceptable. Search problems, TFNP-style.

SymbolNameGroupDefinition given?Why it matters
\(\mathrm{SEARCH}_n\) Unstructured search (relation)
GroverSearch
relational The canonical relation: output any index $i$ with $x_i=1$.
\(\mathrm{Find1}_{\ge n/2}\) FIND-1 under a density promise
promiseFind1
relational The cleanest D-vs-R relational separation: $\mathrm{R}=O(1)$, $\mathrm{D}=n/2+1$.
\(\mathrm{ApproxHW}\) Approximate Hamming weight
ApproxHW
relational Total search problem with $\mathrm{R}=O(1)$ but $\mathrm{psD}=\Omega(n)$: reproducibility is exponentially expensive.
\(\mathrm{AGREE}_n\) Correlated-string search
AgreeString
relational The GLSS19 relational counterexample to composition: $\mathrm{R}=\Theta(\sqrt n)$ but $\mathrm{noisyR}=\Theta(1)$, adaptively and non-adaptively.
\(\mathrm{Search}(\varphi)\) SearchCNF
SearchCNF
relational The canonical TFNP-style query relation: given an assignment, output a falsified clause.
\(\mathrm{AndOr}_{\mathcal{H},t}\) Ben-David-Kundu total search problems
BDKrelation
relational A total search problem with $\mathrm{Q} = \Omega(\sqrt n\log^4 n)$ but conical junta degree $O(\log^7 n)$ -- exponential, and against a measure usually larger than $\mathrm{R}$.
\(S_{\mathrm{YZ}}\) Yamakawa-Zhandry problem
YamakawaZhandry
relational Verifiable exponential quantum advantage for an NP search problem relative to a random oracle.
\(\mathrm{WT}_n\) Welded trees
GluedTrees
relational The quantum-walk speedup: $\mathrm{Q} = \Theta(n)$ against $\mathrm{R} = \mathrm{D} = \tilde\Theta(2^{n/2})$ -- exponential in the tree height, but only $\tilde\Theta(\sqrt{N})$ in the vertex count.
\(\mathrm{LS}(\{0,1\}^n)\) Local search on the hypercube
LocalSearchCube
relational The query-complexity home of PLS, and tight in all three models: $\mathrm{D} = \Theta(2^n/\sqrt n)$, $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$, $\mathrm{Q} = \Theta(2^{n/3}n^{1/6})$.
\(\mathrm{LS}([k]^d)\) Local search on the grid
LocalSearchGrid
relational Tight at $\Theta(k^{d/2})$ randomized for $d\ge4$ and $\Theta(k^{d/3})$ quantum for $d\ge6$; the low dimensions took another decade, and $d=4$ quantum is still open.
\(\mathrm{FFish}_N\) Fourier fishing
FourierFishing
relational The largest separation there is: one quantum query against $\Omega(N/\log N)$ randomized ones -- impossible for a decision problem.
\(\mathrm{Ts}(G)\) Tseitin search on an expander
TseitinExpander
relational The family critical block sensitivity was invented for: $\mathrm{cbs} = \Theta(n)$, and here it really does match $\mathrm{R}$ and $\mathrm{D}$.