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
- \(\mathrm{CG}^{\mathrm{pub}}(f)\) $\mathrm{CA}(f) = \Theta(\mathrm{CG}^{\mathrm{pub}}(f))$ CGLMSG23
- \(\mathrm{fbs}(f)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ ABIKPS17
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.
The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |