Q The Query Complexity Zoo
\(\mathrm{COL}_n\)

Collision problem

$\mathrm{Q}=\Theta(n^{1/3})$ vs $\mathrm{R}=\Theta(\sqrt n)$: a polynomial-only quantum speedup for a promise problem.

partial quantum arity: a function table $g:[n]\to[n]$

Description

Promise: $g$ is one-to-one or two-to-one. Decide which.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n^{1/3})\) Upper: the birthday-paradox-plus-Grover algorithm of [BHT98]. Lower: the polynomial method [AaronsonShi04], originally for range $\Omega(n^2)$; [Kutin05] removed the range restriction (their proof needed range $\ge 3n/2$) and simplified the argument, and [Ambainis05smallrange] handles small ranges too. BHT98 AaronsonShi04 Kutin05
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(\sqrt n)\) Birthday paradox both ways.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(n^{1/3})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(\sqrt n)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\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.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(1)\) The certificate complexity barrier at its sharpest: a collision pair certifies a $2$-to-$1$ input with $2$ queries, and the promise means $O(1)$ queries also certify $1$-to-$1$-ness against the promise, so $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = O(1)$ while $\mathrm{Q} = \Theta(n^{1/3})$. No positive-weight adversary matrix can prove anything here -- this promise problem is the reason the negative-weights version had to be invented. HoyerSpalek05 SpalekSzegedy06
\(\mathrm{D}(f)\) Deterministic query complexity \(n/2+1\) putative Exactly. Upper: a two-to-one $g$ takes only $n/2$ values, so any $n/2+1$ queries repeat one; a one-to-one $g$ never does. Lower: an adversary answering with fresh values keeps both promises alive for $n/2$ queries, since $k \le n/2$ distinct answers can always be extended to a two-to-one function (put the $k$ queried points in $k$ different pairs).
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n/2+1\) putative The same $n/2+1$ positions, fixed in advance.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(n/2+1\) putative Zero error means finishing on a certificate, and certifying one-to-one-ness takes $n/2+1$ distinct answers (see $\mathrm{C}$). So $\mathrm{R}_0 = \Theta(\mathrm{R}^2)$ here: the birthday paradox is a bounded-error phenomenon and nothing else.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(\sqrt n)\) putative Sampling $c\sqrt n$ positions is non-adaptive and finds a collision with constant probability; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(\sqrt n)$. Adaptivity is worth nothing here.
\(\mathrm{C}(f)\) Certificate complexity \(n/2+1\) putative $\mathrm{C}^0 = n/2+1$ by the extension argument above; $\mathrm{C}^1 = 2$, a colliding pair.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(2\) putative A colliding pair, on the two-to-one side.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(n/2+1\) putative The one-to-one side: $n/2$ distinct answers can always be extended to a two-to-one $g$, so nothing short of $n/2+1$ certifies injectivity against the promise.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(2\) putative The two-to-one side: one colliding pair.
\(\mathrm{s}(f)\) Sensitivity \(0\) putative Counting a query as one evaluation of $g$. Changing $g$ at a single point never stays in the promise: from a one-to-one $g$ it creates at most one collision, while a two-to-one $g$ needs all $n/2$ pairs to collide; from a two-to-one $g$ it orphans exactly one pair. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = n/2+1$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(0\) putative See $\mathrm{s}$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(0\) putative See $\mathrm{s}$.
\(\mathrm{bs}(f)\) Block sensitivity \(2\) putative Crossing between the two sides forces a change in each of the $n/2$ pairs, so every sensitive block has $\ge n/2$ of the $n$ coordinates: at most two disjoint ones, and two transversals of the pairing achieve it. $\mathrm{bs}^0 = \mathrm{bs}^1 = 2$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(2\) putative See $\mathrm{bs}$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(2\) putative See $\mathrm{bs}$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(2\) putative Fractionally the same: $(n/2)\sum_B w_B \le \sum_i \mathrm{load}(i) \le n$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(2\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(1)\) putative $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$: rejecting one fixed input of the other type needs only a random query into a block where the two differ. Against $\mathrm{R} = \Theta(\sqrt n)$ and $\mathrm{Q} = \Theta(n^{1/3})$, this is why no certificate-style bound can prove anything about the collision problem.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n/2+1\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $n/2+1$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(n/2+1\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $n/2+1$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(O(n)\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: a two-to-one $g$ has $n/2$ collision pairs, so the width-$2$ collision certificates overlap heavily and no unambiguous family of constant width covers that side.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(\sqrt n)$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(0\) putative Exactly the argument recorded at \(\mathrm{SIMON}_n\): a rectangle $\prod_i S_i$ of functions that contains a $1$-$1$ function $g$ and a two-to-one function $h$ also contains the hybrids that copy one, then two, of $h$'s colliding positions into $g$, and one of those two hybrids has exactly one repeated value -- neither $1$-$1$ nor two-to-one, hence off the promise. So every product distribution inside the promise is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(\sqrt n)$. Contrast \(\mathrm{ED}_n\), the total version, where the uniform product distribution gives $\mathrm{D}^{\mathrm{prod}} = \Theta(n)$: the promise, not the collision structure, is what kills the measure.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\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.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(n^{1/3})\) The [AaronsonShi04]/[Kutin05] lower bound is a degree bound -- that is what the polynomial method proves -- so $\widetilde{\deg} = \Omega(n^{1/3})$; and $\widetilde{\deg} \le 2\mathrm{Q} = O(n^{1/3})$. Approximate degree is thus the tight measure for the collision problem, where $\mathrm{Adv}$ collapses to $O(1)$. AaronsonShi04 Kutin05
\(\deg(f)\) Exact degree \(\Omega(n^{1/3})\) $\deg \ge \widetilde{\deg} = \Omega(n^{1/3})$, in the standard encoding of the table by indicator variables $x_{i,v}$.
\(\mathrm{sdeg}(f)\) Sign degree \(O(n^{1/3})\) $\mathrm{sdeg} \le \widetilde{\deg}_{+} \le \widetilde{\deg} = O(n^{1/3})$.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(O(n^{1/3})\) Between $\mathrm{sdeg}$ and $\widetilde{\deg} = O(n^{1/3})$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(n^{1/3})\) $\mathrm{rdeg}_\varepsilon \le \widetilde{\deg}_\varepsilon = O(n^{1/3})$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(n^{1/3})\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n^{1/3})$. MahadevdeWolf15
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(2\) putative Exactly $2$: the polynomial $\sum_{i<j}\sum_v x_{i,v}x_{j,v}$ counts colliding pairs, so it is nonzero precisely on the two-to-one side, and no linear form can do that. Equivalently $\mathrm{ndeg} \le \mathrm{C}^1 = 2$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = 1$: one nondeterministic quantum query, against $\mathrm{Q} = \Theta(n^{1/3})$ and $\mathrm{R} = \Theta(\sqrt n)$. Guessing a colliding pair is free; finding one is not.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(1)\) $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$; a colliding pair is a two-query certificate and the promise makes it checkable. Aaronson08
\(\lambda(f)\) Spectral sensitivity \(0\) putative The sensitivity graph on the promise is empty (see $\mathrm{s} = 0$: no single change of the table stays inside the promise), so $\lambda = 0$ while $\mathrm{Q} = \Theta(n^{1/3})$. Huang's $\deg \le \lambda^2$ is a total-function theorem.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(1)\) putative Both players output the same uniformly random position $i$. A two-to-one $g$ and a one-to-one $g'$ can agree only on a set where $g$ is injective, i.e. on at most one point of each of the $n/2$ pairs, so they differ on $\ge n/2$ positions and the strategy wins with probability $\ge 1/2$. Hence $\mathrm{CG}^{\mathrm{pub}} \le 2$, and $\ge \mathrm{fbs} = 2$. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(1)\) Between $1$ and $\mathrm{CG}^{*}$. CGLMSG23
\(\mathrm{CA}(f)\) Classical adversary bound \(\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
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(O(n)\) putative Private coins: both players output a uniformly random position, winning with probability $|\Delta|/n^2 \ge 1/(2n)$. The total-function sandwich $\mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1 = O(n)$ happens to give the same bound but is not available on a promise problem, so the strategy is the proof. From below only $\Omega(\mathrm{CG}^{\mathrm{pub}}) = \Omega(1)$. CGLMSG23
\(\mathrm{EC}(f)\) Expectational certificate complexity \(O(\sqrt n)\) putative Uniform weights $w_i = \sqrt{2/n}$: two inputs of different value differ in $\ge n/2$ positions, so their weighted product is $\ge 1$, at cost $\sqrt{2n}$. From below $\mathrm{EC} \ge \mathrm{fbs} = 2$. Not via $\mathrm{EC} \le \mathrm{C}$, which is a total-function statement.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) putative With $1$ = "two-to-one": an algorithm that is certain on the $1$-side never outputs $0$ on a two-to-one input, so whenever it does output $0$ it must hold a $0$-certificate, i.e. $n/2+1$ distinct values. It must do so with probability $\ge 2/3$ on one-to-one inputs, so $\mathrm{R}^1 = \Omega(n)$; and $\mathrm{R}^1 \le \mathrm{D} = n/2+1$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(O(n)\) At most $\mathrm{R}_0 = n/2+1$; at least $\mathrm{Q} = \Omega(n^{1/3})$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(n)\) At most $\mathrm{D} = n/2+1$; at least $\mathrm{Q}_0 = \Omega(n^{1/3})$.
\(\chi(f)\) Conflict complexity \(O(\sqrt n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt n)$. The lower bound $\chi = \Omega(\mathrm{bs})$ [Li18] is total-only and would give only $\Omega(1)$ anyway.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Omega(n^{1/4})\) $\mathrm{R} = O(\bar\chi^2)$ holds for partial $g$, so $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/4})$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt n)$.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(n^{1/4})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR} \le \mathrm{R} = O(\sqrt n)$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(1)\) The reason sabotage complexity is a total-function measure. A one-to-one table and a two-to-one table can agree on at most one point of each of the $n/2$ pairs, so they differ in $\ge n/2$ of the $n$ cells (the same counting as $\mathrm{CG}^{\mathrm{pub}}$ above). Every sabotaged input therefore carries $\ge n/2$ stars, and one uniformly random query finds a star with probability $\ge 1/2$: $\mathrm{RS} \le 2$. From below $\mathrm{RS} \ge \mathrm{CA} = \Omega(1)$. [BenDavidKothari18, Sec. 1.4] state it exactly so -- "any sabotaged input to the collision problem has at least half the bits sabotaged making $\mathrm{RS}(f) = O(1)$, but $\mathrm{R}(f) = \Omega(\sqrt n)$" -- as the reason their quadratic upper bound $\mathrm{R} = O(\mathrm{RS}^2\log\mathrm{RS})$ has to assume totality. BenDavidKothari18
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Omega(n^{1/3})\) $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(n^{1/3})$ since quantum query complexity composes perfectly, and $\mathrm{R}^{*} \le \mathrm{R} = O(\sqrt n)$. Whether iterated collision-finding costs $n^{1/3}$ or $n^{1/2}$ per level is open.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(\sqrt n)\) Between $\widetilde{\deg} = \Theta(n^{1/3})$ and $\mathrm{R} = \Theta(\sqrt n)$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(O(\sqrt n)\) $\mathrm{noisyR} \le \mathrm{R}$. The implication "$\mathrm{R} = \Theta(\text{arity}) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$" does not apply, since $\mathrm{R} = \Theta(\sqrt n)$ and the arity is $n$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Theta(\sqrt n)\) Between $\mathrm{R}$ and $O(\mathrm{R}\log\mathrm{R})$: repeat each read $O(\log n)$ times to make the whole transcript reliable.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(\sqrt n)\) $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(\sqrt n)$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(\sqrt n)\) $\overline{\mathrm{prt}} \le \mathrm{prt}$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\widetilde\Theta(n^{1/3})\) Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$.
\(\mathrm{rank}(f)\) Decision tree rank \(O(n)\) At most $\mathrm{D} = n/2+1$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(\sqrt n)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(\sqrt n)$. (The search version -- find a collision -- is the one where pseudo-determinism bites; the decision version has a unique answer.)
\(\mathrm{cbs}(S)\) Critical block sensitivity \(2\) Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. GoosPitassi14
\(\mathrm{rdeg}(f)\) Rational degree \(O(n)\) At most $\mathrm{C} = n/2+1$; from below $\mathrm{rdeg} \ge \mathrm{ndeg} = 2$ and $\mathrm{rdeg} \ge \widetilde{\mathrm{rdeg}}$.

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 53 in total, strongest first.

… and 39 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Cited as a witness by