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

Multiplicative adversary

A multiplicative-weight version of the adversary method, at least as strong as Adv^pm.

Definition

Replaces the additive progress measure by a multiplicative one; it is at least as strong as $\mathrm{Adv}^{\pm}$ and applies to bounds with small success probability (strong direct product theorems), where $\mathrm{Adv}^{\pm}$ degrades.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{MAdv}(f)\). “\(\mathrm{MAdv}(f)\) in terms of it” is the pair with \(\mathrm{MAdv}(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{MAdv}(f)\) in terms of it It in terms of \(\mathrm{MAdv}(f)\)
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{Adv}(f)\) Positive-weights adversary bound total2,6 partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm total1,1 partial1,? derived open pair → total1,1 partial1,1 derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = \Theta(\sqrt n)$. Spalek08
AND total \(\Theta(\sqrt{n})\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt{n})$ here.
PARITY total \(n/2\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = n/2$. Spalek08
MAJORITY total \(\Theta(n)\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = \Theta(n)$. Spalek08
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta\!\big(\sqrt{k(n-k+1)}\big)$ here.
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(\sqrt n)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here. Spalek08
ADDRESS / multiplexer total \(\Theta(k)\) Also $\Theta(\mathrm{Q})$ for every $f$, and $\mathrm{Q} = \Theta(k)$ here.
Binary tree navigation total \(\Theta(k)\) Squeezed: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(k)$ here.
TRIBES total \(\Theta(\sqrt n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here.
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(n) = \Theta(\sqrt N)$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt{N})$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(2^d)$ here.
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants; the window is that of \(\mathrm{Q}_{\varepsilon}(f)\).
Rubinstein's function total \(\Theta(\sqrt N) = \Theta(n)\) Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants at $\Theta(\sqrt N)$ here.
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4})\) putative Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants; the window is that of \(\mathrm{Q}_{\varepsilon}(f)\).
AND composed with NOT-EXACT-HALF total \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants at $\Theta(n^{3/2})$ here.
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants; both are $\Omega(118.3^{\,d})$ here.
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $f_{2m,m}$: $\mathrm{MAdv}=\Theta(\mathrm{Q})$, so the multiplicative adversary is as small as the algorithm.
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})=\widetilde\Theta(n)$. Unlike the positive adversary below, the multiplicative adversary does see the full hardness.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{Adv}^{\pm}\le\mathrm{MAdv}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$.
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$.
Ambainis' exact-quantum function total \(\Theta(2.1213^d)\) Squeezed between $\mathrm{Adv}^{\pm}$ and $O(\mathrm{Q})$, which coincide.
FORRELATION partial \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\mathrm{Adv}^{\pm}(f) = \Theta(1)$ and $\mathrm{Q}_{\varepsilon}(f) = 1$ here.
k-FORRELATION partial \(\Theta(\lceil k/2\rceil)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\mathrm{Adv}^{\pm}(f) = \Theta(\lceil k/2\rceil)$ and $\mathrm{Q}_{\varepsilon}(f) = \lceil k/2\rceil$ here.
Simon's problem partial \(\Theta(n)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both ends $\Theta(n)$.
Deutsch-Jozsa partial \(1\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}_E$, with both ends $1$.
Bernstein-Vazirani partial \(1\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}_E$, with both ends $1$.
Marked bit partial \(\Theta(\sqrt n)\) Sandwiched between $\mathrm{Adv}^{\pm} = \Theta(\sqrt n)$ and $\mathrm{Q} = \Theta(\sqrt n)$.
Unstructured search (relation) relation \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = \Theta(\sqrt n)$. Spalek08
FIND-1 under a density promise relation \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both $\Theta(1)$.
Approximate Hamming weight relation \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both $\Theta(1)$.
SearchCNF relation \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, and both ends are $\Theta(1)$ here.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$.
Gap-Majority at constant gap partial \(\Theta(1)\) Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$.
Parity-labelled FIND-1 partial \(\Theta(1)\) Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$.
Approximate index partial \(O(\sqrt{k\log k})\) Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$.
Collision problem partial \(\Theta(n^{1/3})\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(n^{1/3})$ here.
Element distinctness total \(\Theta(n^{2/3})\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$ and $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_\varepsilon)$, so the multiplicative adversary is $\Theta(\mathrm{Q})$ on every function; here $\mathrm{Q} = \Theta(n^{2/3})$. Spalek08
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Sandwiched from below: $\mathrm{MAdv} \ge \mathrm{Adv}^{\pm} = \Omega(n^{1/3})$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, and the recorded $\mathrm{Adv}^{\pm}$ is already $\widetilde\Omega(\sqrt n)$.
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both $\mathrm{poly}(n)$.
Surjectivity total \(\tilde\Theta(n)\) Same sandwich as \(\mathrm{Adv}^{\pm}(f)\): the multiplicative adversary is also a tight characterisation of $\mathrm{Q}$.
$k$-distinctness total \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· $\mathrm{MAdv}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{MAdv}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here.
Triangle finding total \(\Omega(m),\ O(m^{5/4})\) Squeezed between $\mathrm{Adv}^{\pm}$, which the multiplicative adversary dominates, and $\mathrm{Q}$, which it lies below -- and those two have the same open window here. So the strengthening from additive to multiplicative buys nothing on the triangle problem either: any improvement would be an improvement to $\mathrm{Q}$.
Recursive Fourier sampling partial \(\Theta(2^{\ell})\) Same sandwich as \(\mathrm{Adv}^{\pm}(f)\): the multiplicative adversary is also a tight characterisation of $\mathrm{Q}$.
Welded trees relation \(\Theta(n)\)· Between $\mathrm{Adv}^{\pm} = \Theta(n)$ (the multiplicative adversary is at least as strong) and $\mathrm{Q} = \Theta(n)$ (every adversary bound is a lower bound on $\mathrm{Q}$). Same medium-confidence caveats as the $\mathrm{Adv}^{\pm}$ and $\gamma_2$ rows.
Local search on the hypercube relation \(\Theta(2^{n/3}n^{1/6})\)· Squeezed between $\mathrm{Adv}^{\pm} = \Theta(2^{n/3}n^{1/6})$, which the multiplicative adversary dominates, and $\mathrm{Q} = \Theta(2^{n/3}n^{1/6})$, which every adversary bound is below. Medium confidence for the same definedness reason as $\gamma_2$.
Local search on the grid relation \(\Theta(k^{d/3})\ (d \ge 6)\)· Squeezed between $\mathrm{Adv}^{\pm} = \Theta(k^{d/3})$, which it dominates, and $\mathrm{Q} = \Theta(k^{d/3})$, which it is below. Same definedness caveat as $\gamma_2$.
Fourier fishing relation \(\Theta(1)\)· Between $\mathrm{Adv}^{\pm} = \Theta(1)$, which it dominates, and $\mathrm{Q} = 1$, which it is below. Same definedness caveat as $\gamma_2$.
Ordered search partial \(\Theta(\log n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\mathrm{E}}(f)$, with both ends $\Theta(\log n)$ here.
Tseitin search on an expander relation \(O(\sqrt n)\)· The multiplicative adversary is also a tight characterisation of $\mathrm{Q}$, so it inherits the $O(\sqrt n)$ ceiling; the characterisation is usually stated for functions, hence the reduced confidence in the relational reading.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(m^{3/2}) = \Theta(\sqrt N)$ here.
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$, which are $\Theta$ of each other and open in the same range here.
Scorpion graphs total \(\Omega(\sqrt m),\ O(m)\) Squeezed between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which are equal up to constants and known here only to $[\Omega(\sqrt m), O(m)]$.
Graph connectivity total \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(m^{3/2}) = \Theta(N^{3/4})$ here.