\(\mathrm{ED}_n\)
Element distinctness
$\mathrm{Q}=\Theta(n^{2/3})$ vs $\mathrm{R}=\Theta(n)$; a total (non-Boolean-input) function.
total quantum arity: $n$ symbols from a large alphabet
Description
Decide whether all $n$ input symbols are distinct.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(n^{2/3})\) | Upper: the quantum walk of [Ambainis07]. Lower: the polynomial method [AaronsonShi04], which needs alphabet size $\Omega(n^2)$; [Ambainis05smallrange] gets $\Omega(n^{2/3})$ down to alphabet size $n$. The $\varepsilon$-dependence is $\Theta(n^{2/3}\log^{1/3}(1/\varepsilon))$ [SherstovThaler23]. Ambainis07 AaronsonShi04 Ambainis05smallrange |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n)\) | |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n\) | |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(n^{2/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^{2/3})$ here. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\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. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\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 |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(\sqrt n)\) | A colliding pair is a $2$-query certificate, but distinctness itself needs all $n$ values: with the convention $\mathrm{ED}_n = 1$ on all-distinct inputs, $\mathrm{C}^1 = n$ and $\mathrm{C}^0 = 2$. The barrier caps the product, so $\mathrm{Adv} \le \sqrt{2n} = O(\sqrt n)$ -- short of $\mathrm{Q} = \Theta(n^{2/3})$, but not the $O(1)$ that a one-sided reading of the barrier would suggest. See \(\mathrm{COL}_n\) for the case where the collapse really is total. SpalekSzegedy06 Zhang05 HoyerSpalek05 |
| \(\mathrm{C}(f)\) Certificate complexity | \(n\) putative | Certifying distinctness requires reading every symbol -- leave one out and it could duplicate another -- so one side of the function has $\mathrm{C} = n$, while a repeated pair certifies the other side in $2$ queries. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(2\) putative | A repeated pair. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(n\) putative | $\mathrm{ED}_n = 1$ means all distinct, and no proper subset of the symbols certifies that: whatever is left unread could duplicate something. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(2\) putative | A colliding pair. This is the lopsided pair of certificate complexities that defeats the positive-weight adversary -- see the \(\mathrm{Adv}(f)\) entry. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(n\) putative | At an all-distinct input, overwriting $x_i$ with $x_j$ flips the answer for every $i$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(2\) putative | A $0$-input can only be fixed by one symbol change if it has exactly one colliding pair $\{i,j\}$ and is otherwise distinct, and then only $i$ and $j$ are sensitive; every other $0$-input is less sensitive still. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(n\) putative | The $n$ singleton blocks at an all-distinct input. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(2\) putative | A block disjoint from the unique colliding pair cannot break the collision, so the two singletons $\{i\},\{j\}$ are all there is. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n\) | Every symbol is relevant, so a non-adaptive algorithm reads all of them -- which here costs nothing, since $\mathrm{D}=n$ anyway. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(n)\) | Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| \(\mathrm{s}(f)\) Sensitivity | \(n\) putative | Counting a query as one symbol read. At an all-distinct input every one of the $n$ coordinates is sensitive: overwrite $x_i$ with $x_j$ for any $j \ne i$ and the answer flips. So $\mathrm{s} = n$, and unlike the promise problems in this file the total function \(\mathrm{ED}_n\) is as sensitive as it can be. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(n\) putative | The $n$ singleton blocks above are disjoint, and $\mathrm{bs} \le n$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(n\) putative | Between $\mathrm{bs} = n$ and $n$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(n\) | Equal to $\mathrm{fbs}$ by LP duality. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(n)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(n)$; also squeezed between $\mathrm{fbs}$ and $\mathrm{R} = \Theta(n)$. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\Theta(n)\) | Squeezed between $\mathrm{fbs} = n$ and $\mathrm{C} = n$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(n\) putative | Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(n\) putative | Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(n)\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ collision certificates (which live on the $0$-side under the convention $\mathrm{ED}_n = 1$ on all-distinct inputs) do not give $O(1)$: an input with many repeats has many such pairs and the family must disambiguate them. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(n)\) | By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(n)$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\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)$. |
| \(\deg(f)\) Exact degree | \(n\) putative | Encode a symbol $x_i$ by the indicators $x_{i,v}$, one block per position; every function on $\Sigma^n$ is then multilinear of degree $\le n$, via $\sum_x f(x)\prod_i x_{i,x_i}$. For the matching lower bound restrict the domain to $x_i \in \{0, i\}$, where $0$ is a fixed symbol and the $i$ are pairwise distinct: writing $z_i = [x_i = 0]$, the input is all-distinct exactly when at most one $z_i$ is $1$, so $\mathrm{ED}_n$ restricts to $\lnot\mathrm{Th}^n_2$ on a Boolean cube of full dimension. That is a non-constant symmetric function whose univariate interpolant takes the values $1,1,0,\dots,0$, with leading coefficient proportional to $1 - n \ne 0$, hence degree exactly $n$. Restriction cannot raise degree, so $\deg(\mathrm{ED}_n) = n$: on the exact-degree scale there is no speedup at all, in sharp contrast with $\widetilde{\deg} = \Theta(n^{2/3})$. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(n^{2/3})\) | Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(n^{2/3})$ by the polynomial method applied to the walk of [Ambainis07]. Lower: the $\Omega(n^{2/3})$ bound of [AaronsonShi04] is a degree bound -- it is proved by symmetrising a low-degree approximating polynomial -- and [Ambainis05smallrange] brings it down to alphabet size $n$. So $\widetilde{\deg}$ is the tight measure here while $\deg = n$. AaronsonShi04 Ambainis05smallrange Ambainis07 |
| \(\mathrm{sdeg}(f)\) Sign degree | \(O(n^{2/3})\) | $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} = O(n^{2/3})$. No matching lower bound is recorded: sign degree ignores the size of the approximation error, and the $\Omega(n^{2/3})$ argument does not survive that relaxation. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(O(n^{2/3})\) | Between $\mathrm{sdeg}$ and $\widetilde{\deg} = O(n^{2/3})$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(n^{2/3})\) | $\mathrm{rdeg}_{\varepsilon} \le \widetilde{\deg}_{\varepsilon} = O(n^{2/3})$. The exact rational degree is much bigger -- see \(\mathrm{rdeg}(f)\) -- so allowing error is what buys the $n^{1/3}$ factor. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(n^{2/3})\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n^{2/3})$; post-selection buys nothing beyond the ordinary quantum walk here. MahadevdeWolf15 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\Theta(n)\) putative | Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = n$. Lower: restrict to $x_i \in \{0,i\}$ as in the \(\deg(f)\) entry, so that $\mathrm{ED}_n$ becomes "at most one $z_i = 1$". A multilinear $p$ that is nonzero exactly on the $n+1$ points of weight $\le 1$ has Moebius coefficients $c_S = (-1)^{|S|}(a_0 - \sum_{i \in S} a_i)$ for $|S| \ge 1$, where $a_0 = p(0)$ and $a_i = p(e_i)$ are all nonzero. Killing every coefficient of degree $n$ forces $a_0 = \sum_i a_i$, and killing every coefficient of degree $n-1$ forces $a_0 = \sum_{i \ne j} a_i$ for each $j$; together these give $a_j = 0$, a contradiction. Hence $\mathrm{ndeg} \ge n-1$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\Theta(n)\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$ and $\mathrm{ndeg} = \Theta(n)$. Certifying distinctness nondeterministically is as hard as it gets, even though the other side needs only a single colliding pair. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\Theta(n)\) | $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$. The two sides are wildly asymmetric: $\mathrm{ndeg}(\bar f) \le 2$, since $\sum_{i<j}\sum_v x_{i,v}x_{j,v}$ counts colliding pairs and so is nonzero exactly when a collision exists, while $\mathrm{ndeg}(f) = \Theta(n)$. The max is $\Theta(n)$, matching $\mathrm{rdeg} \le \mathrm{C} = n$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Theta(n)\) | Squeezed between $\deg/2 = n/2$ and $\mathrm{D} = n$. Exact quantum query complexity gets no asymptotic speedup on element distinctness, while bounded error gets $n^{2/3}$ -- the whole advantage lives in the error. BBCMdW01 |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(n)\) | A zero-error algorithm is in particular a nondeterministic one for both $f$ and $\bar f$, so $\mathrm{Q}_0 \ge \mathrm{NQ} = \Theta(n)$; and $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = \Theta(n)$. So the $n^{2/3}$ walk really does need two-sided error: forbidding it costs the full $n^{1/3}$ factor. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt n)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{RC}})$ and $\mathrm{RC} = \Theta(n)$. Directly: at an all-distinct $x$ every adversary $y$ with $\mathrm{ED}(y) = 0$ differs from $x$ in one symbol, so distinguishing $x$ from all of them is unstructured search, $\mathrm{RC}_x = \Theta(n)$ and $\mathrm{QC}_x = \Theta(\sqrt n)$. Note $\mathrm{QC} = \Theta(\sqrt n)$ sits below $\mathrm{Q} = \Theta(n^{2/3})$: verifying is easier than deciding. Aaronson08 |
| \(\lambda(f)\) Spectral sensitivity | \(\Theta(\sqrt n)\) putative | Take the sensitivity graph on the Hamming graph of $\Sigma^n$. Restricting to the subcube $x_i \in \{0,i\}$ of the \(\deg(f)\) entry keeps single-symbol changes adjacent, so the restricted sensitivity matrix is a principal submatrix and $\lambda(\mathrm{ED}_n) \ge \lambda(\lnot\mathrm{Th}^n_2) \ge \sqrt{\deg(\lnot\mathrm{Th}^n_2)} = \sqrt n$ by [Huang19], which applies because the restriction is a total Boolean function. Above, $\lambda \le \mathrm{Adv} = O(\sqrt n)$. Huang19 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Theta(n)\) putative | Upper: a randomized algorithm of cost $\mathrm{R}$ is a distribution over leaves, i.e. a width-$\mathrm{R}$ conical junta, so $\mathrm{cjdeg} \le \mathrm{R} = O(n)$. Lower: restrict to $x_i \in \{0,i\}$, which sends every block literal to a $z$-literal or a constant and hence maps conical juntas to conical juntas of no greater width. Let $h = \sum_C \alpha_C C$ have width $d$ and approximate "at most one $z_i = 1$". Only all-negative conjunctions fire at $z = 0$, so those carry total weight $\ge 2/3$; each such $C$, of support $S$, also fires at a weight-$2$ input $e_i + e_j$ unless $S$ meets $\{i,j\}$, which for a uniformly random pair happens with probability $\le 2d/n$. Averaging, $1/3 \ge (2/3)(1 - 2d/n)$, so $d \ge n/4$. This separates $\mathrm{cjdeg} = \Theta(n)$ from $\widetilde{\deg} = \Theta(n^{2/3})$: non-negativity costs the whole gap. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(n)\) | Squeezed between $(1-4\varepsilon)\mathrm{CA} + \log\varepsilon = \Omega(n)$ and $2\mathrm{R} = O(n)$. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(n)\) | The relaxation keeps every classical lower bound the partition bound subsumes, in particular $\Omega(\mathrm{bs}) = \Omega(n)$, and $\overline{\mathrm{prt}} \le \mathrm{prt} = \Theta(n)$. KLLRX15 |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Theta(n)\) | The sandwich $\max\{\mathrm{Adv}^2, \mathrm{R}_0, \mathrm{CA}\} \le \mathrm{CG} \le \min\{\mathrm{C}^0\mathrm{C}^1, O(\mathrm{EC}^2)\}$ needs a total function, and this one is total: $\mathrm{R}_0 = \Theta(n)$ below and $\mathrm{C}^0\mathrm{C}^1 = 2n$ above. Note how tight the certificate-product bound is here precisely because the two sides are lopsided -- compare \(\mathrm{forr}\), where the same product is worthless. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(n)\) | $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = \Theta(n)$. Unlike the promise problems in this file, the public-coin game gains nothing over the private-coin one here. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(n)\) | Between $\mathrm{CG}^{\mathrm{ns}}$ and $\mathrm{CG}^{\mathrm{pub}}$, both $\Theta(\mathrm{CA}) = \Theta(n)$. |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(n)\) | All three shared-resource variants collapse to $\Theta(\mathrm{CA}) = \Theta(n)$; only private coin can escape, and here it does not. |
| \(\chi(f)\) Conflict complexity | \(\Theta(n)\) | $\chi = \Omega(\mathrm{bs}) = \Omega(n)$ for total functions [Li18], and $\chi \le \bar\chi \le \mathrm{LR} \le \mathrm{R} = O(n)$. Li18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(n)\) | Squeezed between $\chi = \Theta(n)$ and $\mathrm{LR} \le \mathrm{R} = O(n)$, so the whole composition-theorem family is tight here and $\mathrm{R}(f \circ \mathrm{ED}^m) = \Omega(\mathrm{R}(f)\,n)$. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(n)\) | Between $\bar\chi = \Theta(n)$ and $\mathrm{R} = \Theta(n)$. Element distinctness composes perfectly on the randomized side, unlike the partial functions above where $\mathrm{LR}$ can drop to $\sqrt{\mathrm{R}}$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(n)\) | Between $\mathrm{CA} = \Theta(n)$ and $\mathrm{R} = \Theta(n)$; equivalently $\bar{\mathrm{R}} \ge (1-2\varepsilon)\mathrm{RS}$ above and $\bar\chi = \Omega(\mathrm{RS})$ is consistent below. BenDavidKothari18 |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(n)\) | $\mathrm{R}^* \ge \Omega(\mathrm{LR}) = \Omega(n)$ and $\mathrm{R}^* \le \mathrm{R} = O(n)$, so repeated self-composition loses nothing. BBGM22 |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(\Theta(n)\) putative | Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = O(n)$. Lower: take $\mu$ to be $n$ independent uniform symbols from an alphabet of size $n^2$ -- a product distribution. By the birthday bound the input is all-distinct with probability $e^{-1/2} + o(1)$, so both answers have constant mass, and because the coordinates are i.i.d. adaptivity is useless: after $q$ symbol-reads the algorithm has seen a collision with probability at most $\binom{q}{2}/n^2$, and otherwise its posterior is the same as at the start. Erring with probability $\le 1/3$ therefore needs $q = \Omega(n)$. This is worth recording because $\mathrm{D}^{\mathrm{prod}}$ can be far below $\mathrm{R}$ -- a collision is a correlation between two coordinates, which product distributions cannot plant on purpose, yet the birthday paradox plants one for free. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(n)\) | Degenerate on a total function: only one correct answer, so $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(n)$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(n\) | Degenerate on a Boolean-valued function: every input is critical and the solution function is forced, so $\mathrm{cbs} = \mathrm{bs} = n$. GoosPitassi14 |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\widetilde\Theta(n)\) | Sandwiched: $\mathrm{R} \le \mathrm{N}_p = O(\mathrm{R}\log \mathrm{R})$, with $\mathrm{R} = \Theta(n)$. Setting the noise rate to $0$ recovers the ordinary model, and majority-voting each read $O(\log n)$ times is the generic upper bound. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(n)\)· | Upper: $\mathrm{noisyR} \le \mathrm{R}$. Lower: the recorded $\mathrm{R} = \Theta(n)$ is linear in the arity, and the zoo entry for \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) records $\mathrm{R}(f)=\Theta(n) \Rightarrow \mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ -- at the top of the range there is no room for fractional queries. Contrast \(\mathrm{COL}_n\), where $\mathrm{R} = \Theta(\sqrt n)$ and the shortcut is unavailable. CKMPSS23 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Theta(n^{2/3})\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log\mathrm{Q})$, with $\mathrm{Q} = \Theta(n^{2/3})$. A noisy oracle costs at most a log factor. |
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. 11 in total.
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^0(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{C}^0(f) = 2\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{Adv}(f_n)^{2}\big)\)from \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Adv}(f) = O(\sqrt n)\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) = \Omega\big(\lambda(f_n)^{1.3333}\big)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(n^{2/3})\) against \(\lambda(f) = \Theta(\sqrt n)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{bs}^0(f) = 2\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) = \Omega\big(\mathrm{Adv}(f_n)^{1.3333}\big)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(n^{2/3})\) against \(\mathrm{Adv}(f) = O(\sqrt n)\)
-
\(\mathrm{Q}_{0}(f_n) = \Omega\big(\overline{\mathrm{prt}}_{\varepsilon}(f_n)\big)\)from \(\mathrm{Q}_{0}(f) = \Theta(n)\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(n)\)
-
\(\mathrm{NQ}(f_n) = \Omega\big(\overline{\mathrm{prt}}_{\varepsilon}(f_n)\big)\)from \(\mathrm{NQ}(f) = \Theta(n)\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(n)\)
-
\(\widetilde{\deg}_{\varepsilon}(f_n) = \Omega\big(\mathrm{CG}(f_n)^{0.6667}\big)\)from \(\widetilde{\deg}_{\varepsilon}(f) = \Theta(n^{2/3})\) against \(\mathrm{CG}(f) = \Theta(n)\)
-
\(\mathrm{rdeg}(f_n) = \Omega\big(\overline{\mathrm{prt}}_{\varepsilon}(f_n)\big)\)from \(\mathrm{rdeg}(f) = \Theta(n)\) against \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(n)\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{RS}(f_n)\big)\)from \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{RS}(f) = \Theta(n)\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{CG}(f_n)\big)\)from \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{CG}(f) = \Theta(n)\)
Notes
A reminder that the "total function" theory in this zoo is for Boolean inputs; large alphabets change the picture (here $\mathrm{R}=\Theta(\mathrm{Q}^{3/2})$, which is fine, but the polynomial-relation proofs are alphabet-sensitive).