Simon's problem
The first exponential quantum speedup for a promise problem: $\mathrm{Q}=O(n)$ vs $\mathrm{R}=\Omega(2^{n/2})$.
partial quantum arity: $n2^n$ bits (a function table $g:\{0,1\}^n\to\{0,1\}^n$)
Description
Promise: $g$ is either injective, or two-to-one with $g(x)=g(x\oplus s)$ for a hidden $s\ne 0$. Decide which (or, in the search version, find $s$).
Formal definition
Input: the table of $g:\{0,1\}^n\to\{0,1\}^n$. Promise: either $g$ is injective, or $\exists s \ne 0^n$ with $g(x)=g(y) \iff y \in \{x, x\oplus s\}$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(n)\)· | Simon's algorithm gives $O(n)$; the matching $\Omega(n)$ quantum lower bound is also known, so the exponential speedup is exactly quadratic-free: $\mathrm{R} = 2^{\Theta(\mathrm{Q})}$. Simon97 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(2^{n/2})\) | Simon97 |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(2^{n/2})\) | $\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(2^{n/2})$ here. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(1)\) | Both certificate complexities are $O(1)$ under the promise -- exhibiting one colliding pair $x \ne y$ with $f(x)=f(y)$ settles the question -- so the positive adversary gives $O(1)$ against $\mathrm{Q} = \Theta(n)$. The largest known gap between $\mathrm{Adv}$ and $\mathrm{Q}$. HoyerSpalek05 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(2^{n/2})\) putative | Both directions are about difference sets. Upper: query $A\cup B$ where $A = \{(u,0^{n/2})\}$ and $B = \{(0^{n/2},v)\}$, which is $2^{n/2+1}-1$ points whose pairwise differences $(u,0)\oplus(0,v)=(u,v)$ exhaust $\mathbb{F}_2^n$; a two-to-one $g$ with shift $s$ must therefore repeat a value inside $A\cup B$, and an injective one never does. Lower: an adversary answering with fresh distinct values survives as long as some shift is unexcluded, and $q$ queries exclude only the $\binom q2$ shifts realised as differences, so $q = \Omega(2^{n/2})$. Note this matches $\mathrm{R}$: the birthday paradox buys randomness nothing here, because covering all $2^n$ differences deterministically is just as cheap. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\Theta(2^{n/2})\) putative | The $A\cup B$ query set above is fixed in advance, so the deterministic upper bound is already non-adaptive; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(2^{n/2})\) putative | Sampling $O(2^{n/2})$ uniformly random points is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(2^{n/2})$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(2^{n/2})\) | Sandwiched: $\mathrm{R}_{\varepsilon} \le \mathrm{R}_0 \le \mathrm{D}$, both ends $\Theta(2^{n/2})$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(2^{n/2})\) putative | A certificate for an injective $g$ must exclude every shift $s\ne 0$, i.e. exhibit for each $s$ a queried pair $x, x\oplus s$ with different values; a set of $q$ positions realises at most $\binom q2$ differences, so $q \ge 2^{n/2}$, and the $A\cup B$ set above attains it. A two-to-one $g$ certifies in two queries, so $\mathrm{C}^0$ and $\mathrm{C}^1$ are wildly asymmetric here. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(2\) putative | On a two-to-one input, one colliding pair. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Theta(2^{n/2})\) putative | The injective side. See $\mathrm{C}$: a certificate must exhibit, for every shift $s \ne 0$, a queried pair $x, x\oplus s$ with $g(x) \ne g(x \oplus s)$, and $q$ queried points realise only $\binom q2$ differences. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(2\) putative | The two-to-one side: one colliding pair $g(x) = g(y)$, $x \ne y$, already rules out injectivity, and the promise then forces the answer. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | Counting a query as one evaluation of $g$, as everywhere in this entry. Changing $g$ at a single point never stays inside the promise: from an injective $g$ it can create at most one collision, and a two-to-one function needs all $2^{n-1}$ pairs to collide; from a two-to-one $g$ it orphans exactly one pair, leaving a function that is neither injective nor two-to-one. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ against $\mathrm{D} = \Theta(2^{n/2})$. |
| \(\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 | Every sensitive block has size $\ge 2^{n-1}$: crossing between the injective and the two-to-one side requires touching each of the $2^{n-1}$ pairs $\{x, x\oplus s\}$ at least once. Two disjoint blocks of exactly that size exist -- the two transversals of the pairing -- and three do not fit in $2^n$ points. So $\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 | The fractional relaxation buys nothing: every sensitive block has $\ge 2^{n-1}$ of the $2^n$ coordinates, so $2^{n-1}\sum_B w_B \le \sum_i \mathrm{load}(i) \le 2^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)$: to reject one fixed input of the other kind it is enough to query a random point of a block on which the two differ, which succeeds with constant probability. Rejecting them one at a time is free; $\mathrm{R} = \Theta(2^{n/2})$ is the price of rejecting all of them at once. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\Theta(2^{n/2})\) putative | Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(2^{n/2})$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\Theta(2^{n/2})\) putative | Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(2^{n/2})$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(2^{n/2})\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = \Theta(2^{n/2})$, and nothing sharper is available. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: the cheap two-query collision certificates on the "periodic" side are massively ambiguous, since a periodic $g$ contains $2^{n-1}$ of them, and disambiguating them by "first collision in lex order" costs the full $\Theta(2^{n/2})$ again. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(2^{n/2})\) | By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(2^{n/2})$. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(0\) putative | The support of a product distribution is a rectangle $\prod_i S_i$ of oracle functions, and no rectangle inside the promise meets both sides. Suppose it held a $1$-$1$ function $g$ and a two-to-one function $h$, and let $h(i) = h(j) = v$ with $i \ne j$. The hybrid agreeing with $h$ at $i$ and with $g$ elsewhere lies in the rectangle, so it must be on the promise, which forces it to be $1$-$1$, i.e. $v \notin g(\mathrm{dom} \setminus \{i\})$. But then the hybrid agreeing with $h$ at both $i$ and $j$ and with $g$ elsewhere -- also in the rectangle -- takes the value $v$ exactly twice and every other value once, so it is neither $1$-$1$ nor two-to-one. Hence every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, an exponential gap below $\mathrm{R} = \Theta(2^{n/2})$. See \(\mathrm{forr}\) for the general form of this collapse. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(n)$. Against $\mathrm{Adv} = O(1)$ this is the largest known gap between the positive and the general adversary. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(n)\) | Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both ends $\Theta(n)$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(n)\) | $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(n)$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$, and independently $\mathrm{QC} \le \mathrm{Q}$. Against $\mathrm{C} = \Theta(2^{n/2})$ this is an exponential quantum-certificate advantage: a constant-size quantum certificate replaces a difference-covering set. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) putative | Spectral sensitivity is at most sensitivity for partial $f$, and $\mathrm{s} = 0$ here: the sensitivity graph on the promise has no edges. So $\lambda = 0$ while $\mathrm{Q} = \Theta(n)$. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\Theta(1)\) | At most $\mathrm{C}^1 = 2$, the colliding pair: put $p = \sum_{x<y} \mathbb{1}[g(x) = g(y)]$, a degree-$2$ polynomial in the indicator variables that is $0$ on injective inputs and positive on two-to-one ones. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(1\) | $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = 1$: one nondeterministic quantum query guesses a colliding pair. Against $\mathrm{R} = \Theta(2^{n/2})$. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(n)\) | $\widetilde{\deg} \le 2\mathrm{Q} = O(n)$, in the indicator variables $\mathbb{1}[g(x) = v]$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(O(n)\) | At most $\widetilde{\deg}_+ \le \widetilde{\deg} = O(n)$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(O(n)\) | At most $\widetilde{\deg} = O(n)$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O(n)\) | At most $\widetilde{\deg} = O(n)$, a rational function with denominator $1$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(n)\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n)$. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(2^{n/2})\) | Sandwiched: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, both $\Theta(2^{n/2})$. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(O(2^{n/2})\) putative | Directly, not through $\mathrm{C}$: put $w^g_x = 2^{-(n-1)/2}$ at every one of the $2^n$ points. Two promise inputs of different value differ at $\ge 2^{n-1}$ points (turning a two-to-one $g$ into an injective one requires touching each of its $2^{n-1}$ colliding pairs), so $\sum_{x : g(x)\ne g'(x)} w^g_x w^{g'}_x \ge 1$, and each weight vector sums to $\sqrt 2\,2^{n/2}$. The textbook bound $\mathrm{EC} \le \mathrm{C}$ is a total-function statement and is not used. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(1)\) putative | The shared-randomness strategy needs nothing but the code distance: both players output the same uniformly random point $x$ of the domain of $g$, and win iff $g(x) \ne g'(x)$. Two promise inputs of different value differ at $\ge 2^{n-1}$ of the $2^n$ points, so this wins with probability $\ge 1/2$ and $\mathrm{CG}^{\mathrm{pub}} \le 2$. In general $\mathrm{CG}^{\mathrm{pub}}(f) \le n/d$ where $d$ is the least Hamming distance between two domain points of different value. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(1)\) | Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(1)\) | Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(1)\)· | From $\mathrm{CA} = \Theta(\mathrm{CG}^{\mathrm{pub}})$ [CGLMSG23] and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$ above; and $\mathrm{CA} \ge 1$. So the classical adversary bound is constant while $\mathrm{R} = \Theta(2^{n/2})$ -- Simon's problem is an extreme instance of the [CGLMSG23] observation that $\mathrm{R}$ can be exponentially larger than $\mathrm{CA}$ on partial functions. Every query resolves half of the surviving alternatives, so no adversary distribution can survive. CGLMSG23 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Omega(2^{n/4})\) | $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$, and $\mathrm{LR} \le \mathrm{R} = \Theta(2^{n/2})$. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Omega(2^{n/4})\) | $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ even for partial $g$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. |
| \(\chi(f)\) Conflict complexity | \(O(2^{n/2})\) | $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(O(2^{n/2})\) | From $\mathrm{RS} = O(\bar\chi) = O(\mathrm{LR}) = O(\mathrm{R})$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(O(2^{n/2})\) | $\mathrm{R}^{*} \le \mathrm{R}$; from below $\mathrm{R}^{*} = \Omega(\mathrm{LR}) = \Omega(2^{n/4})$ and $\mathrm{R}^{*} = \Omega(\mathrm{Q}) = \Omega(n)$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(O(2^{n/2})\) | At most $\mathrm{R}$. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(2^{n/2})\) putative | At least $\mathrm{R}$; and reading each sampled point $O(1)$ times and majority-voting each of the $n$ output bits costs only $O(\log n)$ per read, absorbed into the $\Theta(2^{n/2})$. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\widetilde\Theta(n)\) | Between $\mathrm{Q} = \Theta(n)$ and $\mathrm{Q}\log\mathrm{Q} = O(n\log n)$. So the exponential separation survives a noisy oracle. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(O(2^{n/2})\) | Sandwiched between $\widetilde{\deg} = O(n)$ and $\mathrm{R}_\varepsilon = \Theta(2^{n/2})$. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(O(2^{n/2})\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(O(2^{n/2})\) | From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(2^{n/2})\) | Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(2^{n/2})$, since the decision version has a unique correct answer. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(2\) | Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. GoosPitassi14 |
| \(\deg(f)\) Exact degree | \(O(n)\) putative | Exponentially below $\mathrm{D}$. Let $z_{i,v}$ be the degree-$n$ conjunction of input bits asserting $g(i) = v$. Then $P = \sum_{i<j}\sum_v z_{i,v}z_{j,v}$ counts colliding pairs, so $P = 0$ on injective tables and $P = 2^{n-1}$ on two-to-one tables, and $2^{1-n}P$ represents $f$ exactly on the promise with degree $2n$ in the input bits. Beware: $P$ is wildly unbounded off the promise, so this does not bound $\widetilde{\deg}$, which is separately $O(n)$ from $2\mathrm{Q}$. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(O(2^{n/2})\) | At most $\mathrm{C} = \Theta(2^{n/2})$; from below $\mathrm{rdeg} \ge \mathrm{ndeg} = \Theta(1)$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(O(2^{n/2})\) | At most $\mathrm{D} = \Theta(2^{n/2})$, at least $\mathrm{Q} = \Theta(n)$. Simon-style interference gives no exact algorithm: the hidden shift is only recovered with bounded error. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(O(2^{n/2})\) | Sandwiched: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = O(2^{n/2})$. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(O(2^n)\) putative | Private coins. An injective $g$ and a two-to-one $g^{\prime}$ must differ on at least $2^{n-1}$ of the $2^n$ table entries: for each of the $2^{n-1}$ pairs $\{x, x\oplus s\}$ we have $g^{\prime}(x)=g^{\prime}(x\oplus s)$ but $g(x)\ne g(x\oplus s)$, so at least one of the two entries moves. Both players output a uniformly random entry, winning with probability $\ge 2^{n-1}/(2^n)^2$. Contrast $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$: this is another unbounded private-versus-public certificate-game gap, as on \(\mathrm{DJ}_n\). |
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. 158 in total, strongest first.
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{CA}(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(2^{n/2})\) against \(\mathrm{CA}(f) = \Theta(1)\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{pub}}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = \Theta(2^{n/2})\) against \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(1)\)
-
\(\mathrm{UC}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{UC}(f) = \Theta(2^{n/2})\) against \(\mathrm{C}^1(f) = 2\)
-
\(\mathrm{SP}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{SP}(f) = \Theta(2^{n/2})\) against \(\mathrm{C}_{\min}(f) = 2\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{*}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(2^{n/2})\) against \(\mathrm{CG}^{*}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = \Theta(2^{n/2})\) against \(\mathrm{NQ}(f) = 1\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{ns}}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(2^{n/2})\) against \(\mathrm{CG}^{\mathrm{ns}}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{ndeg}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(2^{n/2})\) against \(\mathrm{ndeg}(f) = \Theta(1)\)
-
\(\mathrm{Q}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{fbs}(f_n) = O(1)\)from \(\mathrm{Q}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{fbs}(f) = 2\)
-
\(\mathrm{Q}^{\mathrm{rob}}(f_n) \to \infty \ \text{ while } \ \mathrm{RC}(f_n) = O(1)\)from \(\mathrm{Q}^{\mathrm{rob}}(f) = \widetilde\Theta(n)\) against \(\mathrm{RC}(f) = \Theta(1)\)
-
\(\mathrm{Adv}^{\pm}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{Adv}^{\pm}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = 0\)
-
\(\gamma_2^{\alpha}(f_n) \to \infty \ \text{ while } \ \mathrm{FC}(f_n) = O(1)\)from \(\gamma_2^{\alpha}(f) = \Theta(n)\) against \(\mathrm{FC}(f) = 2\)
-
\(\mathrm{MAdv}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{MAdv}(f) = \Theta(n)\) against \(\mathrm{cbs}(S) = 2\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{CG}^{\mathrm{pub}}(f_n) = O(1)\)from \(\mathrm{C}(f) = \Theta(2^{n/2})\) against \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(1)\)
… and 144 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Exponential: $\mathrm{R} = 2^{\Omega(\mathrm{Q})}$. The relational (find-$s$) version gives the same separation for relations.
-
Unbounded: $\mathrm{C}_{\min}=2$ while $\mathrm{C}=\Theta(2^{n/2})$ -- the two-to-one side certifies in one pair, the injective side needs a difference-covering set.