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.
| Symbol | Name | Group | Definition 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 |
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 |
A generic transformation turning a partial-function separation into a total-function separation. | ||
| \(f_{\mathrm{BHT}}\) | Low-sensitivity function from unambiguous certificates
BHTfn |
The current record for D-vs-s: $\mathrm{D} = \widetilde\Omega(\mathrm{s}^3)$. | ||
| \(f_{\mathrm{BBGJK}}\) | Unambiguous-DNF / Alon-Saks-Seymour function
BBGJKfn |
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 |
Separates C from RC quadratically -- with no log loss -- and RC from bs by a $3/2$ power. | ||
| \(g_n\) | Random-indicator gadget
GSSinner |
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 |
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 |
Randomized analogue of GPW: $\mathrm{R}_0, \mathrm{R} = \widetilde\Omega(\deg^2)$. | ||
| \(\mathrm{NE}^d\) | Ambainis' exact-quantum function
Ambainis13fn |
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 |
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 |
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 |
Log-free optimal separation $\mathrm{C}=\Theta(\mathrm{R}_{\mathrm{RP}}^2)$. | ||
| \(\mathrm{AIKCS}\) | Ambainis–Iraids–Kokainis certificate cheat sheet
AIKCheatSheet |
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 |
$\mathrm{C}^0=\Omega(n^2)$ and $\mathrm{UC}^1=O(n)$, without logarithmic losses. | ||
| PabbarajuQuartic | Pabbaraju’s quartic approximate-degree function
PabbarajuQuartic |
$\mathrm{C}\ge\Omega(\widetilde{\deg}^{\,4}/\log^6 n)$; settles the exponent at four. | ||
| \(\mathrm{PabCS}\) | Pabbaraju’s certificate–sensitivity separator
PabbarajuCubicSensitivity |
Log-free $\mathrm{C}=\Omega(\mathrm{s}^3)$. | ||
| OpenAINestedTournament | OpenAI’s nested tournament sensitivity separator
OpenAINestedTournament |
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 |
$\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 |
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.
| Symbol | Name | Group | Definition 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 |
The universal "hardest easy" promise problem; characterises noisy randomized complexity. | ||
| \(\mathrm{GapMaj}^{1/4}_{n}\) | Gap-Majority at constant gap
GapMajConst |
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 |
The decision version of FIND-1: zero-error $O(1)$ against deterministic $n/4+1$. | ||
| \(\mathrm{ApproxIndex}_k\) | Approximate index
ApproxIndex |
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 |
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.
| Symbol | Name | Group | Definition 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}$. |