Q The Query Complexity Zoo
\(\gamma_2^{\alpha}(f)\)

Approximate gamma_2 norm

Factorisation-norm formulation of the general adversary bound.

Definition

$\gamma_2(M) = \min\{\ \max_x\|u_x\|\max_y\|v_y\|\ :\ M_{xy}=\langle u_x,v_y\rangle\}$; the $\alpha$-approximate version allows $M_{xy}$ to be approximated. For query complexity one applies it to the matrix $(1 - 2\cdot[\![x_i\ne y_i]\!])$ style objects; it coincides with $\mathrm{Adv}^{\pm}$ up to constants.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\gamma_2^{\alpha}(f)\). “\(\gamma_2^{\alpha}(f)\) in terms of it” is the pair with \(\gamma_2^{\alpha}(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 \(\gamma_2^{\alpha}(f)\) in terms of it It in terms of \(\gamma_2^{\alpha}(f)\)
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound total1,1 partial1,1 open pair → total1,1 partial1,? derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 open pair → total1,1 partial1,? derived open pair →
\(\mathrm{Adv}(f)\) Positive-weights adversary bound total2,6 partial∞ derived open pair → total1,1 partial1,? derived open pair →
\(\mathrm{MAdv}(f)\) Multiplicative adversary total1,1 partial1,1 derived open pair → total1,1 partial1,? 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})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here.
AND total \(\Theta(\sqrt{n})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here.
PARITY total \(\Theta(\lceil n/2 \rceil)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \lceil n/2 \rceil$ here.
MAJORITY total \(\Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(\sqrt{k(n-k+1)}\big)$ here.
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here.
EXACT-HALF total \(\Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
ODD-MAX-BIT total \(\Theta(\sqrt n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
ADDRESS / multiplexer total \(\Theta(k)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(k)$ here.
Binary tree navigation total \(\Theta(k)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(k)$ here.
TRIBES total \(\Theta(\sqrt n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n) = \Theta(\sqrt N)$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{N})$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^d)$ here.
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim.
Rubinstein's function total \(\Theta(\sqrt N) = \Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(\sqrt N)$ here.
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4})\) putative $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim.
AND composed with NOT-EXACT-HALF total \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/2})$ here.
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative $\gamma_2^{\alpha} = \Theta(\mathrm{Q}_{\varepsilon})$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} \ge 118.3^{\,d}$ here.
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $f_{2m,m}$: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) The approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}$, hence $\Theta(\mathrm{Q})$. LMRSS11
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\Omega(\sqrt n)$. LMRSS11
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\widetilde\Omega(n^{1/4})$. LMRSS11
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})=\widetilde\Omega(n^{1/6})$. LMRSS11
Ambainis' exact-quantum function total \(\Theta(2.1213^d)\) Squeeze: the approximate $\gamma_2$ norm is the factorisation-norm form of $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. LMRSS11
FORRELATION partial \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
k-FORRELATION partial \(\Theta(\lceil k/2\rceil)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(\lceil k/2\rceil)$.
Simon's problem partial \(\Theta(n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(n)$.
Deutsch-Jozsa partial \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
Bernstein-Vazirani partial \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
Two-or-none search partial \(\Theta(\sqrt n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(\sqrt n)$.
Marked bit partial \(\Theta(\sqrt n)\) $\gamma_2^{\alpha} = \Theta(\mathrm{Q})$.
Dense marked bit partial \(\Theta(1)\) $\gamma_2^{\alpha} = \Theta(\mathrm{Q}) = \Theta(1)$.
Unstructured search (relation) relation \(\Theta(\sqrt n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(\sqrt n)$.
FIND-1 under a density promise relation \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
Approximate Hamming weight relation \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
SearchCNF relation \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Adv}^{\pm}) = \Theta(\mathrm{Q}) = \Theta(1)$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) $\gamma_2 = \Theta(\mathrm{Q})$.
Gap-Majority at constant gap partial \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q})$.
Parity-labelled FIND-1 partial \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
Approximate index partial \(O(\sqrt{k\log k})\) $\gamma_2 = \Theta(\mathrm{Q})$.
Collision problem partial \(\Theta(n^{1/3})\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(n^{1/3})$. Note $\mathrm{Adv} = O(1)$ on the same problem: the general adversary is exactly what the positive one cannot see.
Element distinctness total \(\Theta(n^{2/3})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{2/3})$ here.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) $\gamma_2 = \Theta(\mathrm{Q}) = \Omega(n^{1/3})$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) $\gamma_2 = \Theta(\mathrm{Adv}^{\pm}) = \widetilde\Omega(\sqrt n)$.
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \mathrm{poly}(n)$.
Surjectivity total \(\tilde\Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \tilde\Theta(n)$ here.
$k$-distinctness total \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(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})\) The approximate $\gamma_2$ norm equals $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), so it inherits the open window too.
Recursive Fourier sampling partial \(\Theta(2^{\ell}) \text{ for } g = g_{\mathrm{mod}3}\) The approximate $\gamma_2$ norm equals $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), which is $\Theta(\mathrm{Q}_{\varepsilon}) = \Theta(2^{\ell})$ here.
Welded trees relation \(\Theta(n)\)· The approximate $\gamma_2$ norm and $\mathrm{Adv}^{\pm}$ agree up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), and $\mathrm{Adv}^{\pm} = \Theta(n)$ here. Medium confidence for the same two reasons as the $\mathrm{Adv}^{\pm}$ row: $\gamma_2$ is only partially defined on relations, and the $\Omega(n)$ side of $\mathrm{Q}$ is folklore.
Local search on the hypercube relation \(\Theta(2^{n/3}n^{1/6})\)· Equal to $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), which is $\Theta(2^{n/3}n^{1/6})$ here. Medium confidence only because $\gamma_2$ is listed as partially defined on relations.
Local search on the grid relation \(\Theta(k^{d/3})\ (d \ge 6)\)· Equal to $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). Medium confidence only because $\gamma_2$ is listed as partially defined on relations.
Fourier fishing relation \(\Theta(1)\)· Equal to $\mathrm{Adv}^{\pm} = \Theta(1)$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). Medium confidence only because $\gamma_2$ is listed as partially defined on relations.
Ordered search partial \(\Theta(\log n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon} = \Theta(\log n)$ here. Note the contrast with the positive-weights $\mathrm{Adv} = \Theta(1)$ on this page: the certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = 2$ bites, and only the general adversary escapes it.
Tseitin search on an expander relation \(O(\sqrt n)\)· The approximate $\gamma_2$ norm equals $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), which is $O(\sqrt n)$ here.
Inner product mod 2 total \(\Theta(n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(\sqrt N)$ here.
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)); see \(\mathrm{Adv}^{\pm}(f)\).
Scorpion graphs total \(\Omega(\sqrt m),\ O(m)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), which is pinned only to $[\Omega(\sqrt m), O(m)]$ here.
Graph connectivity total \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(N^{3/4})$ here.