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

Classical adversary bound

The classical analogue of the positive-weights quantum adversary; a lower bound on R.

also written: relational adversary, Aaronson adversary, Laplante-Magniez Kolmogorov bound

Definition

Aaronson's classical adversary: choose a relation $\mathcal{R}$ between 0-inputs and 1-inputs and weights; the bound is the resulting min-max quantity. Several apparently different formulations (Aaronson's, the Laplante-Magniez Kolmogorov version, the "weighted" version) all coincide.

Basic facts

  • $\mathrm{CA}(f) = O(\mathrm{R}(f))$ for every (partial) Boolean $f$.
  • $\mathrm{CA}(f) \le \mathrm{EC}(f)$ always, and $\mathrm{CA}(f) \le \mathrm{RS}(f)$.
  • $\mathrm{EC}(f) \le \mathrm{C}(f)$ for total $f$ only. The proof hands each input the indicator of a minimal certificate as its weight scheme, and checks the constraint on a pair $x,y$ with $f(x) \ne f(y)$ by observing that their certificates must conflict. On a promise problem two certificates can fail to conflict, because the string stitched together from both may simply be outside the domain -- the same step that breaks the \(\mathrm{CG}(f)\) sandwich. On a partial function, prove an $\mathrm{EC}$ upper bound by exhibiting a weighting directly.
  • There are partial functions with $\mathrm{R}(f)$ exponentially larger than $\mathrm{CA}(f)$ [CGLMSG23].

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{CA}(f)\). “\(\mathrm{CA}(f)\) in terms of it” is the pair with \(\mathrm{CA}(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{CA}(f)\) in terms of it It in terms of \(\mathrm{CA}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total2,3 partial∞ relation∞ derived open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total1,1 partial1,? open pair → total1,1 partial1,? open pair →
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) total1,1 partial1,1 open pair → total1,1 partial1,1 open pair →
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) total1,1 partial1,1 derived open pair → total2,4 partial∞ derived open pair →
\(\mathrm{EC}(f)\) Expectational certificate complexity total1,1 partial1,? derived open pair → total1,2 partial∞ derived open pair →
\(\mathrm{Adv}(f)\) Positive-weights adversary bound total2,2 partial2,2 relation2,? open pair → total1,1 partial1,? relation1,? derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(n)$ and $\mathrm{fbs}(f) = n$ here.
AND total \(\Theta(n)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{CA}(f) \le \mathrm{RC}(f)$, with $\mathrm{fbs}(f) = n$ and $\mathrm{RC}(f) = \Theta(n)$ here.
PARITY total \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
MAJORITY total \(\Theta(n)\) The classical adversary equals $\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
Threshold total \(\Theta(\max\{k,\;n-k+1\})\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \max\{k,\;n-k+1\}$ here.
Symmetric functions (general) total \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(n)$ here. ABIKPS17
EXACT-HALF total \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \lfloor n/2\rfloor+1$ here. ABIKPS17
ADDRESS / multiplexer total \(\Theta(k+1)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = k+1$ here.
Binary tree navigation total \(\Theta(k)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = k$ here. ABIKPS17
TRIBES total \(\Theta(n/\log n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with both ends $\Theta(n/\log n)$ here.
AND-OR tree (depth 2) total \(\Theta(n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(n)$ and $\mathrm{fbs}(f) = n$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) $\mathrm{CA}(f) = \Theta(\mathrm{RC}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{RC}(f)\)), and $\mathrm{RC}(f) = \Theta(\sqrt{N})$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = 2^d$ here.
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with $\mathrm{RC}(f) = \Theta(N)$ and $\mathrm{fbs}(f) = N$ here.
Rubinstein's function total \(\Theta(N)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(N)$ here.
Ambainis-Sun function total \(\Theta(N)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\Theta(14011^{\,d})\) putative $\mathrm{CA} = \Theta(\mathrm{fbs})$ for every total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a quadratic $\mathrm{Q}$-vs-$\mathrm{CA}$ gap. ABIKPS17
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. Against $\mathrm{C}=\Theta(n^2)$ this is the same quadratic gap the entry is built for, read on the classical adversary bound. ABIKPS17
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3})\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. ABIKPS17
FORRELATION partial \(\widetilde O(\sqrt n)\) The classical adversary lower-bounds $\mathrm{R} = \widetilde\Theta(\sqrt n)$ (via $\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon) \le 2\mathrm{R}_\varepsilon + O(1)$). It is at least $\Omega(\mathrm{fbs})$, which is only $\Omega(1)$ here, so nothing pins it further.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) $\mathrm{CA} = O(\mathrm{R})$; from below only $\mathrm{CA} = \Omega(\mathrm{fbs}) = \Omega(1)$, so nothing pins it.
Simon's problem partial \(\Theta(1)\)· From $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}})$ [CGLMSG23] and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ above; and $\mathrm{CA} \ge 1$. So the classical adversary bound is constant while $\mathrm{R} = \Theta(2^{n/2})$ -- Simon's problem is an extreme instance of the [CGLMSG23] observation that $\mathrm{R}$ can be exponentially larger than $\mathrm{CA}$ on partial functions. Every query resolves half of the surviving alternatives, so no adversary distribution can survive. CGLMSG23
Deutsch-Jozsa partial \(\Theta(1)\) A lower bound on $\mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(\Theta(1)\)· From $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}})$ [CGLMSG23] with $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. Directly: any two codewords disagree on half of the positions, so a uniformly random query kills half of the surviving adversary mass and no weighting scheme can survive $\omega(1)$ queries. The classical adversary bound therefore certifies nothing about $\mathrm{R} = \Theta(n)$. CGLMSG23
Dense marked bit partial \(\Theta(1)\) A lower bound on $\mathrm{R} = \Theta(1)$, and at least $1$.
Unstructured search (relation) relation \(\Theta(n)\)· The relational adversary was designed for exactly this problem and is tight on it: pair $0^n$ with each $e_i$ at weight $1/n$ to get $\Omega(n)$, and $\mathrm{CA} \le \mathrm{R} = \Theta(n)$. Note that $\mathrm{CA}$ lower-bounds $\mathrm{R}$ only, not $\mathrm{Q}$ -- the quantum bound needs \(\mathrm{Adv}(f)\), which stops at $\Theta(\sqrt n)$.
FIND-1 under a density promise relation \(\Theta(1)\) The classical adversary bound is a lower bound on $\mathrm{R}$, which is $O(1)$ here; and it is at least a constant for any non-trivial problem. So the relational adversary, which was designed for search problems, is powerless against \(\mathrm{Find1}_{\ge n/2}\) -- correctly so, since $\mathrm{R} = O(1)$.
Approximate Hamming weight relation \(\Theta(1)\) A lower bound on $\mathrm{R} = \Theta(1)$, and at least a constant.
SearchCNF relation \(\Theta(1)\) A lower bound on $\mathrm{R} = \Theta(1)$, hence $\Theta(1)$. By $\mathrm{cbs} = O(\mathrm{CA})$ [ABK21lifting] this forces \(\mathrm{cbs}(S)\) $= \Theta(1)$ here too: both of these adversary-flavoured measures lower-bound the randomized cost, so neither can see the $\Theta(n)$ deterministic cost. Only \(\mathrm{DTsize}(f)\) and \(\mathrm{D}(f)\) do.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) putative Upper and lower, and neither uses a total-function theorem. Lower: $\mathrm{CA} \ge \mathrm{fbs} = \Theta(\min(n,1/\delta))$, which does survive on partial functions (\(\mathrm{CA}(f)\), settings note). Upper: $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}})$ and the shared-random-index strategy below wins with probability $2\delta$. So $\mathrm{CA}$ sees the $\Theta(1/\delta)$ but not the $\Theta(1/\delta^2)$ of $\mathrm{R}$: the classical adversary bound is quadratically weak exactly where bias-amplification is the real cost. CGLMSG23
Gap-Majority at constant gap partial \(\Theta(1)\) putative Between $\mathrm{fbs}$ and $\mathrm{CG}^{\mathrm{pub}}$, both constant. CGLMSG23
Parity-labelled FIND-1 partial \(\Theta(1)\) A lower bound on $\mathrm{R} = O(1)$, and at least a constant for a non-trivial problem. The classical adversary is powerless here -- correctly, since $\mathrm{R} = O(1)$.
Approximate index partial \(O(\sqrt{k\log k})\) At most $\mathrm{R}$. Since $\mathrm{fbs} = 1$ here, the classical adversary is the only combinatorial measure left with any room, but no lower bound better than $\Omega(1)$ is available.
Collision problem partial \(\Theta(1)\)· $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}}) = \Theta(1)$, with $\mathrm{CA} \ge \mathrm{fbs} = 2$ from below. So both adversary methods fail on the collision problem: the positive quantum one by the certificate barrier ($\mathrm{Adv} = O(1)$) and the classical one for the same combinatorial reason, while $\mathrm{R} = \Theta(\sqrt n)$. CGLMSG23
Element distinctness total \(\Theta(n)\) $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(n)$ for total functions; also $\mathrm{CA} \le \mathrm{R} = \Theta(n)$. So the classical adversary is tight here while the positive quantum adversary caps out at $O(\sqrt n)$.
Ambainis-Belovs function partial \(O(n)\) $\mathrm{CA} \le \mathrm{R} \le \mathrm{D} = O(n)$. From below only $\mathrm{CA} = \Omega(\mathrm{fbs}) = \Omega(1)$, so this is not pinned. Note $\mathrm{CA} = \Theta(\mathrm{fbs})$ is a total-function theorem and must not be used here.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CA}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
$k$-distinctness total \(\Theta(n)\) $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(n)$; also capped by $\mathrm{R} = \Theta(n)$. The classical adversary is tight here even though the positive quantum adversary is not.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CA}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
Local search on the hypercube relation \(\tilde\Theta(2^{n/2})\) Lower: [Aaronson06, Thm. 15] proves $\Omega(2^{n/2}/n^2)$ by exactly the object this measure names -- his classical relational adversary, a weighting of pairs of inputs with different valid answers. Upper: $\mathrm{CA} \le \mathrm{R} = \Theta(2^{n/2}\sqrt n)$. So the classical adversary is tight here up to $n^{2.5}$, and the sharpening to $\Theta(2^{n/2}\sqrt n)$ in [Zhang09localsearch] came from a different (random-walk) argument rather than from a better relation. Aaronson06 Zhang09localsearch
Ordered search partial \(O(\log n)\) $(1-4\varepsilon)\mathrm{CA}\le\mathrm{prt}_\varepsilon+\log(1/\varepsilon)$ for partial functions [JainKlauck10, CGLMSG23], and $\mathrm{prt}\le2\,\mathrm{R}=O(\log n)$. No matching lower bound: $\mathrm{CA}=\Theta(\mathrm{fbs})$ holds only for total functions, and here $\mathrm{fbs}=2$. JainKlauck10 CGLMSG23
Tseitin search on an expander relation \(\Theta(n)\) Squeezed: $\mathrm{cbs} = O(\mathrm{CA})$ [ABK21lifting] gives $\Omega(n)$, and $\mathrm{CA} \le \mathrm{R} = \Theta(n)$ closes it. So on this family the classical adversary is tight, which is exactly the contrast with \(\mathrm{Search}(\varphi)\), where it collapses to $\Theta(1)$. ABK21lifting
Inner product mod 2 total \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^2) = \Theta(N^{2/3})\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ [ABIKPS17], and $\mathrm{fbs} = \Theta(m^2)$ here. A cube-root below $\mathrm{R} = \Theta(N)$: the classical adversary is far from tight on the one-in-a-box function. ABIKPS17
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{CA}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ [ABIKPS17], and $\mathrm{fbs} = \Theta(m)$ here. ABIKPS17
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ [ABIKPS17], and $\mathrm{fbs} = \Theta(m^2)$ here. ABIKPS17