Q The Query Complexity Zoo
\(\mathrm{C}(f)\)

Certificate complexity

Max over inputs of the smallest partial assignment that fixes the value of f.

also written: nondeterministic query complexity, N(f)

Definition

A $b$-certificate is a partial assignment $\rho$ such that $f(y) = b$ for every $y$ in the domain consistent with $\rho$. $\mathrm{C}_x(f)$ is the size of the smallest certificate for $f(x)$ consistent with $x$; $\mathrm{C}(f) = \max_x \mathrm{C}_x(f)$ and $\mathrm{C}^b(f) = \max_{x\in f^{-1}(b)} \mathrm{C}_x(f)$.

$\mathrm{C}^1$ and $\mathrm{C}^0$ are exactly the nondeterministic and co-nondeterministic query complexities.

Basic facts

  • $\mathrm{bs}(f) \le \mathrm{C}(f) \le \mathrm{s}(f)\,\mathrm{bs}(f)$ [Nisan].
  • $\mathrm{D}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f)$ [Blum-Impagliazzo; Hartmanis-Hemachandra; Tardos].
  • $\mathrm{D}(f) \le \mathrm{C}^1(f)\,\mathrm{bs}(f)$ and $\mathrm{D}(f)\le \mathrm{C}^1(f)\deg(f)$ [BBCMdW01].
  • $\mathrm{C}(f) \le \mathrm{D}(f)$ and $\mathrm{C}(f) \ge \mathrm{bs}(f) \ge \mathrm{s}(f)$.
  • The maximum separation from bounded-error randomized queries is quadratic, with no log loss: $\mathrm{C}=\Omega(\mathrm{R}^2)$ on \(\mathrm{AIKuD}\) [AIK26]. Ben-David–Kothari championship function independently gives the same exponent with logarithmic slack [BenDavidKothari26].
  • The $\mathrm{C}/\mathrm{Q}$ and $\mathrm{C}/\widetilde{\deg}$ exponents are settled at $4$, up to logarithms [AIK26, BenDavidKothari26, Pabbaraju26]. Exact and zero-error quantum queries have a quadratic separation from $\mathrm{C}$, against a cubic universal upper bound [AIK26, KLLPV26].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{C}(f)\). “\(\mathrm{C}(f)\) in terms of it” is the pair with \(\mathrm{C}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{C}(f)\) in terms of it It in terms of \(\mathrm{C}(f)\)
\(\mathrm{C}^0(f)\) 0-certificate complexity total∞ partial∞ derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{C}^1(f)\) 1-certificate complexity total∞ partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{bs}(f)\) Block sensitivity total2,2 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 open pair → total2,2 partial∞ relation∞ open pair →
\(\mathrm{RC}(f)\) Randomized certificate complexity total2,2 partial∞ open pair → total1,1 partial1,1 open pair →
\(\mathrm{UC}(f)\) Unambiguous certificate complexity total1,1 partial1,1 derived open pair → total2,2 partial2,? derived open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total2,2 partial∞ relation∞ open pair → total2,2 partial∞ relation∞ open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total4,4 partial∞ relation∞ open pair → total2,2 partial∞ relation∞ open pair →
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity total2,3 partial2,? open pair → total1,1 partial1,1 open pair →

The 9 above are this entry’s hand-picked neighbours; the other 84 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(n\)
AND total \(n\)
PARITY total \(n\)
MAJORITY total \((n+1)/2\)
Threshold total \(\max\{k,\;n-k+1\}\)
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
EXACT-HALF total \(n\) Sandwiched: $\mathrm{s}^1(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) putative A certificate need not pin the highest $1$ -- it only has to force the answer. If the highest $1$ of $x$ is at position $i$, it is enough to fix $x_i = 1$ and to zero out the opposite-parity positions above $i$: $1 + |\{j > i : j \not\equiv i\}|$ coordinates, maximised at $i = 1$ giving $\lfloor n/2\rfloor + 1$. That also matches $\mathrm{bs} = \lfloor n/2\rfloor+1 \le \mathrm{C}$, so the bound is tight. (Verified exhaustively for $n \le 12$.)
ADDRESS / multiplexer total \(k+1\)
Binary tree navigation total \(k\) putative The walk itself is a certificate, and nothing shorter is: omit a node of the walk and the walk is free to leave. So $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = \mathrm{C}_{\min} = \mathrm{D} = k$ -- navigation is completely certificate-uniform, and all the difficulty is in finding the $k$ relevant variables among $2^k-1$.
TRIBES total \(\Theta(n/\log n)\)
AND-OR tree (depth 2) total \(n\)
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\)
Recursive MAJORITY-of-3 total \(2^d\)
Kushilevitz's function (iterated) total \(N\)
Rubinstein's function total \(\Theta(N)\)
Ambainis-Sun function total \(6k^2+7k+2\) putative $\max\{\mathrm{C}^0,\mathrm{C}^1\}$; the $0$-side dominates quadratically.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(14011^{\,d}\) putative Squeezed exactly: $\mathrm{C} \ge \mathrm{bs} \ge \mathrm{bs}^0 = 14011^{\,d}$ from \(\mathrm{bs}^0(f)\), and $\mathrm{C} = \max\{\mathrm{C}^0,\mathrm{C}^1\} = \mathrm{C}^0 = 14011^{\,d}$ from \(\mathrm{C}^0(f)\) and \(\mathrm{C}^1(f)\).
Pointer functions total \(\widetilde\Theta(\sqrt n)\) putative Variant $f_{2m,m}$. Upper: a zero-error algorithm's transcript is a certificate, so $\mathrm{C}\le 2\,\mathrm{R}_0=\widetilde O(\sqrt n)$. Lower: $\mathrm{D}\le\mathrm{C}^2$ against $\mathrm{D}=\widetilde\Omega(n)$. So the $\mathrm{D}$-vs-$\mathrm{R}_0$ separation is simultaneously an extremal $\mathrm{D}=\widetilde\Theta(\mathrm{C}^2)$ family.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) The point of the construction: the outer Block $k$-sum has certificates made of $O(n)$ ones and only $O(k^2\log n)$ zeroes, and the inner $k$-sum certifies ones cheaply, so the composition certifies in $O(k^2\sqrt n\log n)=\widetilde O(\sqrt n)$ bits [ABK16, Thm 10]. The cheat sheet keeps this: certify the $10\log n$ copies and read the one indexed cell. ABK16
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) putative From $\mathrm{D}\le\mathrm{C}^2$ against $\mathrm{D}=\widetilde\Omega(n^3)$. No matching upper bound is known here: all that totality gives is $\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}$ [Nisan91], and the only theorem bounding $\mathrm{bs}$ by $\mathrm{s}$ is $\mathrm{bs}\le 2\deg^2\le 2\mathrm{s}^4$ (Nisan-Szegedy plus Huang), giving $\mathrm{C}\le 2\mathrm{s}^5=\widetilde O(n^5)$. The familiar $\mathrm{bs}\le\mathrm{s}^2$ is an open conjecture, not an available bound.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\ge\mathrm{C}_0$ and $\mathrm{C}\le\mathrm{D}$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{C}\ge\mathrm{C}_0=\Omega(n^2)$ and $\mathrm{C}\le N=n^2$.
Random-indicator gadget total \(n\) Squeeze: $\mathrm{C}=\max\{\mathrm{C}^0,\mathrm{C}^1\}=n$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\ge\mathrm{C}_0$ and $\mathrm{C}\le\mathrm{D}$. Note the asymmetry: $\mathrm{C}_1=\widetilde O(\sqrt n)$ but $\mathrm{C}_0$ is maximal.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeeze: $\mathrm{C}\ge\mathrm{C}_0$ and $\mathrm{C}\le\mathrm{D}$. As in \(f_{\mathrm{GPW}}\) the asymmetry is total: $\mathrm{C}_1=\widetilde O(n^{1/3})$ against a maximal $\mathrm{C}_0$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{bs}\le\mathrm{C}\le n$.
FORRELATION partial \(\Theta(n)\) putative Upper: $\mathrm{C} \le 2n$. Lower, from one explicit $1$-input. Take $n = 2^m$ with $m$ even and let $x$ be a bent function on $m$ bits, so $\hat x_j = \pm n^{-1/2}$ for every $j$; put $y_j = \sqrt n\,\hat x_j \in \{\pm1\}$. Then $\Phi = \tfrac{1}{\sqrt n}\sum_j \hat x_j y_j = 1$, a $1$-input. Dually $\hat y_i = x_i/\sqrt n$, so $\Phi = \tfrac{1}{\sqrt n}\sum_i x_i \hat y_i$ and flipping any single $x_i$ lowers $\Phi$ by exactly $2/n$; flipping $t$ of them gives $\Phi = 1 - 2t/n$ exactly. Choosing $t$ near $n/2$ lands in $|\Phi| \le 1/100$, a $0$-input. So a certificate at this input must fix all but at most $0.51n$ of the $n$ coordinates of $x$, i.e. $\mathrm{C}^1 \ge 0.49n$.
k-FORRELATION partial \(O(kn)\) At most the whole input. Note that the $k = 2$ argument of \(\mathrm{forr}\), which gives $\mathrm{C} = \Theta(n)$ there, does not transfer: for $k \ge 3$ a single bit of a middle block can move $\Phi_k$ by $\Theta(1)$ rather than $O(1/\sqrt n)$, since both $Hx^{\ell-1}$ and $Hx^{\ell+1}$ can spike at the same coordinate.
Simon's problem partial \(\Theta(2^{n/2})\) putative A certificate for an injective $g$ must exclude every shift $s\ne 0$, i.e. exhibit for each $s$ a queried pair $x, x\oplus s$ with different values; a set of $q$ positions realises at most $\binom q2$ differences, so $q \ge 2^{n/2}$, and the $A\cup B$ set above attains it. A two-to-one $g$ certifies in two queries, so $\mathrm{C}^0$ and $\mathrm{C}^1$ are wildly asymmetric here.
Deutsch-Jozsa partial \(N/2+1\) putative From $\mathrm{C}^0$. With $\mathrm{fbs}=2$ this is a much cleaner unbounded $\mathrm{C}$-vs-$\mathrm{fbs}$ witness than any total function can give.
Bernstein-Vazirani partial \(n\) putative A set of queried positions $i_1,\dots,i_k$ reveals $\langle s, i_j\rangle$, and pins $s$ down exactly when the $i_j$ span $\mathbb{F}_2^n$ -- so every certificate has $\ge n$ queries, and $e_1,\dots,e_n$ is one. Since this holds at every input, $\mathrm{C}_{\min} = \mathrm{C} = n$: BV is certificate-uniform.
Unique search partial \(n\)
Two-or-none search partial \(n-1\) putative The maximum of $\mathrm{C}^0 = n-1$ and $\mathrm{C}^1 = 1$.
Marked bit partial \(1\) putative One query, at every input and on both sides. Any marked cell certifies: by the promise no domain input has marks of both colours, so seeing a single $1$-mark rules out every $0$-input and vice versa. This is the sharpest form of the promise-problem lesson -- $\mathrm{D} \le \mathrm{C}^0\mathrm{C}^1$ would read $n \le 1$.
Dense marked bit partial \(1\) putative One query, on both sides: a single marked bit rules out every input of the other value, because the promise forbids marks of both colours. As on \(\mathrm{MARK}_n\), $\mathrm{D} \le \mathrm{C}^0\mathrm{C}^1$ would read $n/2+1 \le 1$.
Unstructured search (relation) relation \(n\) putative Attained only at $0^n$, where the sole valid answer is $\bot$ and certifying it means excluding every index, i.e. reading all $n$ bits. Everywhere else one queried $1$ certifies itself.
FIND-1 under a density promise relation \(1\) putative One queried $1$ certifies its own index as a valid output, at every input. So $\mathrm{C} = 1$ against $\mathrm{D} = n/2+1$: for relations, certificate complexity does not bound deterministic complexity at all, because knowing that a short certificate exists does not tell you where to look.
Approximate Hamming weight relation \(\Theta(n)\) putative A partial assignment fixing $q$ coordinates leaves $|x|$ free in a window of width $n-q$, so it forces a single valid answer only when $n - q \le 2\varepsilon n$, i.e. $q \ge (1-2\varepsilon)n$. Fixing that many coordinates does certify. So even nondeterministically this problem is hard, unlike \(\mathrm{Find1}_{\ge n/2}\) where $\mathrm{C}=1$.
Correlated-string search relation \(\Theta(n)\) putative A partial assignment fixing $q$ coordinates forces a valid answer only if some $y$ works for all $2^{n-q}$ completions, and the worst completion is at distance $n-q$ from $y$; so $q \ge n/2 + \sqrt n$, and that many suffice.
SearchCNF relation \(\Theta(1)\) putative The $k$ variables of a falsified clause certify that clause, so $\mathrm{C} \le k = O(1)$ at every assignment. So $\mathrm{C} = \Theta(1)$ against $\mathrm{D} = \Theta(n)$: a falsified clause is trivially verifiable and yet, by the resolution-depth lower bound, very far from findable. This is the query-complexity shadow of TFNP.
Gap-Majority partial \(\Theta(n)\) Exactly $n/2 - \delta n + 1$ on both sides, for every $\delta$. A $1$-certificate must fix that many ones: fix fewer and setting all free coordinates to $0$ leaves a completion that is still inside the promise and is a $0$-input. Symmetrically for $\mathrm{C}^0$. Note this is not $\Theta(\mathrm{D})$ by accident -- here $\mathrm{C}$, $\mathrm{C}^0$, $\mathrm{C}^1$ and $\mathrm{D}$ all coincide up to the additive $1$.
Gap-Majority at constant gap partial \(\Theta(n)\) Exactly $n/4 + 1$ on both sides: a $1$-certificate must exhibit that many ones, or setting every free coordinate to $0$ leaves a $0$-input of the promise.
Parity-labelled FIND-1 partial \(1\) putative One queried $1$ certifies the answer at every input: if $x_i = 1$ with $i$ odd then no $0$-input of the promise agrees, since $0$-inputs vanish on all odd coordinates. So $\mathrm{C} = 1$ against $\mathrm{D} = n/4+1$ -- the certificate is as short as it can be and locating it is the entire problem.
Approximate index partial \(\Theta(1)\) putative One array cell. By the promise, a cell holding a value in $\{0,1\}$ must lie in the ball around $a$, so reading any non-$2$ cell both locates you inside the ball and reads off the answer -- two bits after the binary encoding. So $\mathrm{C} = \Theta(1)$ against $\mathrm{D} = \Theta(\sqrt{k\log k})$: the difficulty is entirely in finding a good cell, never in recognising one.
Collision problem partial \(n/2+1\) putative $\mathrm{C}^0 = n/2+1$ by the extension argument above; $\mathrm{C}^1 = 2$, a colliding pair.
Element distinctness total \(n\) putative Certifying distinctness requires reading every symbol -- leave one out and it could duplicate another -- so one side of the function has $\mathrm{C} = n$, while a repeated pair certifies the other side in $2$ queries.
Ambainis-Belovs function partial \(O(n)\) Reading all $3n$ variables is a certificate for either side. Nothing smaller is proved, and note that certificate complexity is not a lower-bound technique that could reach $\Omega(n^{1/3})$ anyway: $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1}$ is already known to be $O(1)$ here.
Ben-David-Kundu total search problems relation \(O(\log^6 n)\) putative A valid output is a tuple $(i_1,\dots,i_t)$ of all-$1$ blocks, and exhibiting the $t\log(n/2) = O(\log^6 n)$ bits of those blocks certifies it. Membership in query $\mathrm{TFNP}$ is exactly the requirement that certificates be polylogarithmic in the input size, and it is what makes the $\mathrm{Q} = \widetilde\Omega(\sqrt n)$ lower bound interesting.
Yamakawa-Zhandry problem relation \(n\) putative A solution is a codeword $y \in \mathcal{C} \subseteq \Sigma^n$ with $H(i, y_i) = 1$ for all $i$; exhibiting those $n$ oracle bits certifies it, and fewer will not, since any unfixed coordinate could fail. So $\mathrm{C} = n$ against $\mathrm{D} = 2^{\Omega(n)}$ -- the problem is in the query analogue of $\mathrm{NP}$, which is exactly what makes the quantum advantage verifiable.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The $\mathrm{s}$ end is itself an unpublished argument (see above), so this is only as good as that.
$k$-distinctness total \(n\) $\mathrm{C} = \max(\mathrm{C}^0,\mathrm{C}^1) = \max(n,k) = n$.
Triangle finding total \(\binom m2 = n\) $\mathrm{C} = \max(\mathrm{C}^0,\mathrm{C}^1) = \max(\binom m2, 3)$.
Welded trees relation \(\Theta(1)\) putative Nine queries certify the answer, and this is the cleanest statement of what the welded-trees speedup does not give you. Certificate: query $(y,c)$ for all nine colours $c$ at $y = \pi(\mathrm{EXIT})$. The answers show $y$ has exactly two neighbours. In the welded-trees graph only the two roots have degree $2$; every other vertex has degree $3$, and a name that is not a vertex answers $1^{2n}$ nine times. Since $\pi(\mathrm{ENTRANCE})$ is fixed and known and differs from $y$, every legal instance consistent with those nine cells has $\pi(\mathrm{EXIT}) = y$. So $\mathrm{C} \le 9$ while $\mathrm{D} = \tilde\Theta(2^{n/2})$: verifying the exit is free, finding it is not.
Local search on the hypercube relation \(n+1\) putative Exactly $n+1$, at every input. A local minimum $v$ is certified by $f(v)$ together with its $n$ neighbours, and nothing less will do: drop the neighbour $w$ from the certificate and the completion $f(w) = f(v)-1$ is consistent and makes $v$ invalid. So $\mathrm{C} = n+1 = \log_2 N + 1$ against $\mathrm{D} = \Theta(N/\sqrt{\log N})$ -- an exponential $\mathrm{D}$-vs-$\mathrm{C}$ gap on a total search problem, which is the query-complexity content of "PLS solutions are efficiently verifiable".
Local search on the grid relation \(2d+1 = \Theta(1)\) putative A local minimum is certified by its own value and those of its $\le 2d$ neighbours, and no smaller set will do -- omit a neighbour and it can be completed to a strictly smaller value. With $d$ constant this is $\Theta(1)$ against $\mathrm{D} = \Theta(k^{d-1})$, an unbounded $\mathrm{D}$-vs-$\mathrm{C}$ gap on a total search problem. Compare \(\mathrm{LS}(\{0,1\}^n)\), where the same argument gives $n+1$ because the degree grows.
Fourier fishing relation \(\Theta(N)\) putative At least $N/2$, so the one-query quantum answer is not even checkable cheaply. Fix $q$ cells; they contribute $S_{\mathrm{fix}}$ to $\widehat f(z) = N^{-1/2}\sum_x f(x)(-1)^{x\cdot z}$ with $|S_{\mathrm{fix}}| \le q/\sqrt N$, while the $N-q$ free cells contribute any value on the lattice $\{(N-q-2j)/\sqrt N\}$. If $q \le N/2$ then $(N-q)/\sqrt N \ge |S_{\mathrm{fix}}|$, so some completion has $|\widehat f(z)| \le 1/\sqrt N < 1$ and $z$ is not valid. The promise costs nothing: among uniformly random completions of the free cells $\widehat f(z)$ is essentially a standard Gaussian, so $\Pr[|\widehat f(z)|<1] = \Theta(1)$ while the promise holds with probability $1-o(1)$, and the two events intersect. Upper $\mathrm{C} \le \mathrm{D} = N$.
Ordered search partial \(2\) putative Decision version, $n \ge 2$: $\{x_k = 0,\ x_{k+1} = 1\}$ pins $k$ and hence the answer, and one query cannot. This is what makes the positive adversary useless here.
Tseitin search on an expander relation \(\Theta(1)\) putative The $d = O(1)$ edges incident to a violated vertex certify it. So verification is trivial while $\mathrm{R} = \Theta(n)$ -- the same shape as \(\mathrm{Search}(\varphi)\), and the reason this is a search problem rather than a decision problem in disguise.
Inner product mod 2 total \(n\) As above.
Minsky-Papert one-in-a-box total \(m^2 = N^{2/3}\) $\max\{\mathrm{C}^0,\mathrm{C}^1\}$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) putative $\max(\mathrm{C}^0,\mathrm{C}^1)$; also directly $\mathrm{C} \le \mathrm{D} = O(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) $\max(\mathrm{C}^0, \mathrm{C}^1)$, i.e. the cut side.
Ben-David–Kothari championship function total \(\Omega(n^2)\) Theorem 1 and Lemma 4. BenDavidKothari26
Ambainis–Iraids–Kokainis unambiguous DNF total \(\Theta(n^2)\) Theorem 2.2. AIK26
Ambainis–Iraids–Kokainis certificate cheat sheet total \(\Omega(n^2)\) Theorem 2.1, with explicit lower bound n(⌈n/2⌉+1). AIK26
Pabbaraju’s optimal unambiguous DNF total \(\Theta(n^2)\) C≥C₀ and C≤n². Pabbaraju26
Pabbaraju’s quartic approximate-degree function total \(\Omega(n^2)\) Theorem 4; equation (42). Pabbaraju26
Pabbaraju’s certificate–sensitivity separator total \(\Omega(n^3)\) Appendix C: C⁰(F)≥3u C⁰(f)=Ω(n³). Pabbaraju26
AND of complemented EXACT-ONE functions total \(m^2\) At zero every bit is sensitive; C≥s and C≤m². KLLPV26
Complement of the Ambainis–Iraids–Kokainis DNF total \(\Theta(n^2)\) Certificate complexity is invariant under output complementation; Theorem 2.2. AIK26