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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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. |