Gilmer-Saks-Srinivasan functions
Separates C from RC quadratically -- with no log loss -- and RC from bs by a $3/2$ power.
total arity: $n^2$ bits
Description
Two constructions studying the limits of composition for $\mathrm{C}$, $\mathrm{RC}$ and $\mathrm{bs}$. Both have the shape $\mathrm{OR}_n \circ g$ for a cleverly chosen $n$-variate $g$, exploiting the elementary fact that $\mathrm{OR}$-composition multiplies the $0$-side of $\mathrm{C}$, $\mathrm{bs}$ and $\mathrm{fbs}$ by $n$ while leaving the $1$-side alone.
Formal definition
For the quadratic separation [GSS16, Thm 32]: pick $N = 2^{n/50}$ points $x^1,\dots,x^N \in \{0,1\}^n$ uniformly at random and let $g_n$ be their indicator. With high probability the points are at pairwise Hamming distance $\ge n/100$, which forces every $0$-input to have at most $200$ disjoint sensitive blocks ($\mathrm{bs}_0(g_n),\mathrm{fbs}_0(g_n)=O(1)$), while sheer density makes every subcube of codimension $n/100$ contain a $1$, so $\mathrm{C}_0(g_n)\ge n/100$. Then $f = \mathrm{OR}_n\circ g_n$ on $n^2$ bits. By [GSS16, Prop. 31], for $m\in\{\mathrm{C},\mathrm{bs}, \mathrm{fbs}\}$ one has $m_1(\mathrm{OR}_n\circ g)=m_1(g)$ and $m_0(\mathrm{OR}_n\circ g)=n\cdot m_0(g)$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Theta(n^2)\) | A random $g_n$ has $\mathrm{C}_0(g_n)=\Theta(n)$, and $\mathrm{OR}$-composition multiplies the $0$-side by $n$ [GSS16, Prop. 31, Claim 34]. No logarithmic loss anywhere. GSS16 |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{C}\ge\mathrm{C}_0=\Omega(n^2)$ and $\mathrm{C}\le N=n^2$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(n\) putative | By [GSS16, Prop. 31] $\mathrm{C}_1(f)=\mathrm{C}_1(g_n)$, and $\mathrm{C}_1(g_n)=n$: the $1$-inputs of $g_n$ are isolated points (pairwise distance $\ge n/100$), so every subcube containing one and no $0$-input is a single point. GSS16 |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\Theta(n)\) | Upper: $\mathrm{fbs}(f)\le\max\{n\,\mathrm{fbs}_0(g_n),\mathrm{fbs}_1(g_n)\}=O(n)$, since the pairwise-distance property caps $\mathrm{fbs}_0(g_n)$ at $200$ [GSS16, Thm 32]. Lower: $\mathrm{fbs}\ge\mathrm{bs}\ge\mathrm{bs}_0(f)=n\,\mathrm{bs}_0(g_n)\ge n$. GSS16 |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\Theta(n)\) | Squeezed between $\mathrm{bs}_0(f)=n\,\mathrm{bs}_0(g_n)\ge n$ and $\mathrm{fbs}=O(n)$. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| \(\mathrm{s}(f)\) Sensitivity | \(\Theta(n)\) putative | Upper $\mathrm{s}\le\mathrm{bs}=O(n)$. Lower: take a point $y$ at Hamming distance $1$ from some $x^i$, so $\mathrm{s}_y(g_n)=1$, and feed the copy $(y,\dots,y)$ to $\mathrm{OR}_n\circ g_n$; every one of the $n$ blocks is then sensitive, so $\mathrm{s}_0(f)\ge n$. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{D}\ge\mathrm{C}=\Omega(n^2)$ and $\mathrm{D}\le N=n^2$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n^2\) | Squeeze: $\mathrm{D}\le\mathrm{Dna}\le N=n^2$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$, both $\Theta(n^2)$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$. A zero-error algorithm's transcript is a certificate, so the maximal $\mathrm{C}_0$ pins $\mathrm{R}_0$ at the top; the cheap fractional certificate helps only the bounded-error models. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(n)\) | Squeeze: $\mathrm{CA}=\Theta(\mathrm{fbs})$ for total functions. Against $\mathrm{C}=\Theta(n^2)$ this is the same quadratic gap the entry is built for, read on the classical adversary bound. ABIKPS17 |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\Theta(n)\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt n)\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\Theta(n)\) | Squeeze: the $\mathrm{s}$ line above exhibits a $0$-input with $n$ sensitive blocks-of-size-one, and $\mathrm{s}_0\le\mathrm{s}=O(n)$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\Theta(n)\) | Squeeze: $\mathrm{s}_0\le\mathrm{bs}_0\le\mathrm{bs}=O(n)$. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n^2)\) putative | Not computed in [GSS16], and the fractional certificate leaves it open from below -- $\mathrm{fbs}=\Theta(n)$ only gives $\mathrm{R}=\Omega(n)$. But the family is an $\mathrm{OR}$-composition, so the randomized composition theorem applies: $\mathrm{R}(\mathrm{OR}_n\circ g_n^{\,n})=\Omega(\mathrm{R}(\mathrm{OR}_n)\,\chi(g_n))$ [Sanyal18] (comp-R), and $\chi(g_n)\ge(\mathrm{bs}(g_n)+1)/2$ [Li18, Thm 1] with $\mathrm{bs}(g_n)\ge\mathrm{s}(g_n)=n$, since a $1$-input of $g_n$ is an isolated point. So $\mathrm{R}=\Omega(n\cdot n)=\Omega(n^2)$, and $\mathrm{R}\le\mathrm{D}=n^2$. The cheap fractional certificate buys nothing after all: this family separates $\mathrm{C}$ from $\mathrm{RC}$ quadratically but not from $\mathrm{R}$ at all. Sanyal18 Li18 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=\Theta(n)$. |
| \(\lambda(f)\) Spectral sensitivity | \(O(n)\) | Squeeze: $\lambda\le\mathrm{s}=O(n)$, with the Huang floor $\lambda\ge\sqrt{\mathrm{s}}=\Omega(\sqrt n)$. |
| \(\deg(f)\) Exact degree | \(\Omega(n^{2/3})\) | Squeeze: $\mathrm{D}=O(\deg^3)$ [Midrijanis04] against $\mathrm{D}=\Theta(n^2)$. The inner $g_n$ is a random indicator, so its degree is almost surely full and the true value is presumably $\Theta(n^2)$; only the lower bound is recorded. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(n\) putative | A $1$-input of $g_n$ is an isolated point, so all $n$ of its bits are sensitive; feeding it to one copy of $\mathrm{OR}_n\circ g_n$ with the other $n-1$ copies at $0$-inputs gives $\mathrm{s}_1(f)\ge n$. The ceiling is $\mathrm{s}_1\le\mathrm{C}^1=n$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(n\) putative | Squeezed between $\mathrm{s}_1=n$ and $\mathrm{C}^1=n$. So the whole $\mathrm{C}$-vs-$\mathrm{bs}$ gap of this family lives on the $0$-side, where $\mathrm{C}^0=\Theta(n^2)$ but $\mathrm{bs}_0=\Theta(n)$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(n\) putative | Upper: $\mathrm{C}_{\min}\le\mathrm{C}^1=n$. Lower: a $1$-certificate must pin a whole isolated point of some copy ($n$ bits), and a $0$-certificate must force all $n$ copies to $0$ at $\ge n/100$ bits each; so $\mathrm{C}_x\ge n$ for every input. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Omega(n)\) | A Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}\ge\mathrm{C}_{\min}=n$; the ceiling is $\mathrm{rank}\le\mathrm{D}=\Theta(n^2)$. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(\Omega(n)\) | Squeeze: $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\Theta(n^2)$ (equally, $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=n$). Unlike \(f_{\mathrm{GPW}}\) there is no matching upper bound: the $1$-certificates here are not unambiguous, since several copies can be $1$ at once. BHT17 |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\Omega(n)\) | Squeeze: $\mathrm{EC}\ge\mathrm{fbs}=\Theta(n)$, with ceiling $\mathrm{EC}\le\mathrm{C}=\Theta(n^2)$. Note $\mathrm{R}_0=O(\mathrm{EC}^2)$ gives the same $\Omega(n)$, so the two routes agree and neither closes the gap. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Omega(n^2)\) | Squeeze: $\mathrm{R}_0=O(\mathrm{CG})$ against $\mathrm{R}_0=\Theta(n^2)$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\Theta(n)\) | For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}=\mathrm{bs}=\Theta(n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)). |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{bs}=O(\widetilde{\deg}^2)$ [NS94] with $\mathrm{bs}=\Theta(n)$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Omega(n^{2/3})\) | Squeeze: $\mathrm{Q}_E\ge\deg/2=\Omega(n^{2/3})$, which beats the route through $\mathrm{Q}$; the ceiling is $\mathrm{Q}_E\le\mathrm{D}=\Theta(n^2)$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_E$. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11 |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{MAdv}=\Theta(\mathrm{Q})$. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{R}^1\ge\mathrm{R}=\Omega(n^2)$ by the line above; the ceiling is $\mathrm{D}=\Theta(n^2)$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Omega(n),\ O(n^2)\) | The sabotage inequality runs $\mathrm{R}_\varepsilon\ge\overline{\mathrm{R}}_\varepsilon\ge(1-2\varepsilon)\mathrm{RS}$ [BenDavidKothari18, Thm 12], so $\mathrm{R}$ is the ceiling, $\mathrm{RS}=O(\mathrm{R})=O(n^2)$. The floor is $\mathrm{RS}\ge\mathrm{CG}^{\mathrm{pub}}\ge\mathrm{fbs}=\Theta(n)$, which matches the recorded $\mathrm{R}$ floor. BenDavidKothari18 |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(n^2)\) | Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\Omega(n^2)$; the ceiling is $\mathrm{D}^{\mathrm{na}}=n^2$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(n^2)\) | For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\Theta(n^2)$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Omega(n)\) | The distributional form of $\mathrm{R}$: $\overline{\mathrm{R}}=\Theta(\mathrm{R})=\Omega(n)$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Omega(n)\) | Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\Omega(n)$. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(2^{-\Theta(n)}\) putative | Direct computation. The inner $g_n$ is the indicator of $2^{n/50}$ isolated points, so $\mathrm{I}(g_n)=2^{-n}\sum_x \mathrm{s}(g_n,x)=2^{-n}\cdot 2n\cdot 2^{n/50}=2n\,2^{-49n/50}$. In $f=\mathrm{OR}_n\circ g_n$ a bit is influential only if it flips its own copy and the other $n-1$ copies all evaluate to $0$, an event of probability $1-o(1)$, so $\mathrm{I}(f)=(1\pm o(1))\,n\,\mathrm{I}(g_n)=2^{-\Theta(n)}$. Total influence is therefore exponentially small while $\mathrm{D}=\Theta(n^2)$ -- a reminder that no polynomial bound on $\mathrm{D}$ in terms of $\mathrm{I}$ can exist. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(2^{-\Theta(n)}\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=2^{-\Theta(n)}$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(2^{-\Theta(n)}\) | Squeeze: $\mathrm{MaxInf}\le\mathrm{I}=2^{-\Theta(n)}$, and $\mathrm{MaxInf}\ge\mathrm{I}/n^2$, which changes only the constant in the exponent. |
| \(\mathrm{Var}(f)\) Variance | \(2^{-\Theta(n)}\) | From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry; the exponent is not pinned tightly enough to read off \(\mathrm{osss}(f)\) or \(\mathrm{nsr}(f)\). |
| \(\mathrm{NS}_{\delta}(f)\) Noise sensitivity | \(2^{-\Theta(n)}\) | For any constant $\delta$: $\mathrm{NS}_\delta\le\delta\,\mathrm{I}(f)=2^{-\Theta(n)}$. |
| \(\mathrm{Stab}_{\rho}(f)\) Noise stability | \(1-2^{-\Theta(n)}\) | For any constant $\rho$: $f$ takes the value $1$ with probability $n\,2^{-49n/50}$, so $\Pr[f(x)\ne f(y)]\le 2\Pr[f=1]=2^{-\Theta(n)}$ for correlated $x,y$, giving $\mathrm{Stab}_\rho=1-2^{-\Theta(n)}$ -- the function is essentially constant in the Fourier-analytic sense despite being maximally hard to query. |
| \(\chi(f)\) Conflict complexity | \(\Omega(n),\ O(n^2)\) | Floor $\chi=\Omega(\mathrm{bs})=\Omega(n)$ [Li18]; ceiling $\chi=O(\mathrm{R})=O(n^2)$. The composition-friendly relaxation of $\mathrm{R}$ therefore sees the $\mathrm{bs}$ scale, not the $\mathrm{C}$ scale. Li18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Omega(n),\ O(n^2)\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19] between $\mathrm{RS}=\Omega(n)$ and $\mathrm{R}=O(n^2)$. GLSS19 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Omega(n),\ O(n^2)\) | Squeezed between $\bar\chi=\Omega(n)$ and $\mathrm{R}=O(n^2)$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Omega(n),\ O(n^2)\) | Squeezed between $\mathrm{LR}=\Omega(n)$ and $\mathrm{R}=O(n^2)$; the quantum floor $\mathrm{R}^*=\Omega(\mathrm{Q})=\Omega(\sqrt n)$ is weaker. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Omega(n)\) | Squeeze: $\mathrm{N}_p\ge\mathrm{R}=\Omega(n)$; the ceiling $O(\mathrm{R}\log\mathrm{R})$ adds only $O(n^2\log n)$, which is above the recorded $\mathrm{R}$ ceiling anyway. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{Q}^{\mathrm{rob}}\ge\mathrm{Q}=\Omega(\sqrt n)$ [BNRdW05]. BNRdW05 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(n)\) | The public-coin certificate game value collapses to $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\Theta(n)$ for total functions [ABIKPS17]. Against the recorded $\mathrm{CG}=\Omega(n^2)$ this makes the family a quadratic private-coin-vs-public-coin certificate-game separation with no logarithmic loss. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(n)\) | Same collapse: $\mathrm{CG}^{\mathrm{ns}}=\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\Theta(n)$. ABIKPS17 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(n)\) | Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(n)$. ABIKPS17 |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Omega(n),\ O(n^2)\) | Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\Omega(n)$ (also $\mathrm{prt}_\varepsilon\ge(1-4\varepsilon)\mathrm{CA}+\log\varepsilon$, the same scale); ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=O(n^2)$ [JainKlauck10, Thm 3.1]. The zero-error partition bound is a different story: $\mathrm{prt}_0\ge\mathrm{C}=\Omega(n^2)$. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Omega(n),\ O(n^2)\) | The $\mathrm{RC}$ and $\mathrm{CA}$ floors survive the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over. JainKlauck10 |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Omega(\sqrt n),\ O(n^{3/2})\) | Floor $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02] with $\mathrm{bs}=\Theta(n)$; ceiling the certificate barrier $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}=\sqrt{\Theta(n^2)\cdot n}=O(n^{3/2})$. Ambainis02 |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\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 |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Omega(n)}\) | A decision tree of rank $r$ has at least $2^r$ leaves, so $\mathrm{DTsize}\ge 2^{\mathrm{rank}}$, and the recorded $\mathrm{rank}=\Omega(n)$ (every input needs an $n$-bit certificate) gives an exponential size lower bound. The ceiling is the trivial $2^{\mathrm{D}}=2^{O(n^2)}$. EhrenfeuchtHaussler89 |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(O(n)\) | Squeeze: $\mathrm{ndeg}\le\mathrm{C}^1=n$ -- sum the indicator conjunctions of the $1$-certificates, which are non-negative and cannot cancel. Against $\mathrm{C}=\Theta(n^2)$ this is a clean quadratic gap. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(O(n)\) | Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=O(n)$. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Omega(\sqrt n),\ O(n^2)\) | Floor $\mathrm{cjdeg}\ge\widetilde{\deg}=\Omega(\sqrt n)$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\Theta(n^2)$, a depth-$\mathrm{D}$ tree being an exact conical junta of width $\mathrm{D}$. |
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. 56 in total, strongest first.
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = 2^{\Omega(n)}\) against \(\mathrm{Stab}_{\rho}(f) = 1-2^{-\Theta(n)}\)
-
\(\mathrm{C}(f_n) = \Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{C}(f) = \Theta(n^2)\) against \(\mathrm{QC}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{C}^0(f_n) = \Omega\big(\mathrm{bs}(f_n)^{2}\big)\)from \(\mathrm{C}^0(f) = \Theta(n^2)\) against \(\mathrm{bs}(f) = \Theta(n)\)
-
\(\mathrm{UC}(f_n) = \Omega\big(\mathrm{fbs}(f_n)^{2}\big)\)from \(\mathrm{UC}(f) = \Theta(n^2)\) against \(\mathrm{fbs}(f) = \Theta(n)\)
-
\(\mathrm{SP}(f_n) = \Omega\big(\mathrm{RC}(f_n)^{2}\big)\)from \(\mathrm{SP}(f) = \Theta(n^2)\) against \(\mathrm{RC}(f) = \Theta(n)\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{FC}(f_n)\big)\)from \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Omega(n),\ O(n^2)\) against \(\mathrm{FC}(f) = \Theta(n)\)
-
\(\mathrm{UC}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{UC}(f) = \Theta(n^2)\) against \(\mathrm{Stab}_{\rho}(f) = 1-2^{-\Theta(n)}\)
-
\(\mathrm{C}^0(f_n) = \Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{C}^0(f) = \Theta(n^2)\) against \(\mathrm{QC}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{C}(f_n) = \Omega\big(\mathrm{fbs}(f_n)^{2}\big)\)from \(\mathrm{C}(f) = \Theta(n^2)\) against \(\mathrm{fbs}(f) = \Theta(n)\)
-
\(\mathrm{SP}(f_n) = \Omega\big(\mathrm{bs}(f_n)^{2}\big)\)from \(\mathrm{SP}(f) = \Theta(n^2)\) against \(\mathrm{bs}(f) = \Theta(n)\)
-
\(\overline{\mathrm{prt}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{RC}(f_n)\big)\)from \(\overline{\mathrm{prt}}_{\varepsilon}(f) = \Omega(n),\ O(n^2)\) against \(\mathrm{RC}(f) = \Theta(n)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = \Omega(n)\) against \(\mathrm{Stab}_{\rho}(f) = 1-2^{-\Theta(n)}\)
-
\(\mathrm{UC}(f_n) = \Omega\big(\mathrm{QC}(f_n)^{4}\big)\)from \(\mathrm{UC}(f) = \Theta(n^2)\) against \(\mathrm{QC}(f) = \Theta(\sqrt n)\)
-
\(\mathrm{C}(f_n) = \Omega\big(\mathrm{FC}(f_n)^{2}\big)\)from \(\mathrm{C}(f) = \Theta(n^2)\) against \(\mathrm{FC}(f) = \Theta(n)\)
… and 42 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
$\mathrm{C} = \Omega(\mathrm{RC}^2)$, matching $\mathrm{C}=O(\mathrm{RC}^2)$. Settled, and with no logarithmic loss.
-
$\mathrm{C} = \Omega(\mathrm{bs}^2)$, matching $\mathrm{C} \le \mathrm{s}\cdot\mathrm{bs} \le \mathrm{bs}^2$. Settled, and with no logarithmic loss.
-
$\mathrm{RC} = \Omega(\mathrm{bs}^{3/2})$ against the upper bound $\mathrm{RC} = O(\mathrm{bs}^2)$. This comes from the second construction, not from the values recorded here.
Cited as a witness by
-
\(\mathrm{C}(f_n) = \Omega(\mathrm{bs}(f_n)^2)\)
-
\(\mathrm{C}(f_n) = \Omega(\mathrm{RC}(f_n)^2)\)
-
\(\mathrm{fbs}(f_n) = \widetilde\Omega\big(\mathrm{bs}(f_n)^{3/2}\big)\)
-
\(\mathrm{C}(f_n) = \widetilde\Omega\big(\mathrm{fbs}(f_n)^2\big)\)
Notes
The recorded values are for the first construction, [GSS16, Thm 32], which is the one that settles $\mathrm{C}$ against $\mathrm{RC}$ and against $\mathrm{bs}$. Note that it loses no logarithms: the separations really are $\Omega(\cdot^2)$, not $\widetilde\Omega(\cdot^2)$, which is unusual in this part of the zoo.
The $\mathrm{RC}$-vs-$\mathrm{bs}$ witness is a different function [GSS16, Thm 37], also of the form $\mathrm{OR}_n\circ g$ on $n^2$ bits but with $g$ an explicit graph function due to Tal: the variables are the edges of $K_s$ with $n=\binom s2$, and $g$ has $\mathrm{bs}_0(g)=O(1)$ but $\mathrm{fbs}_0(g)=\Omega(\sqrt n)$, giving $\mathrm{bs}(f)=O(n)$ and $\mathrm{fbs}(f)=\Omega(n^{3/2})$. Its numbers are deliberately not merged into the table above.
[GSS16] phrase all of this in terms of critical exponents $\mathrm{crit}(m_1,m_2)$, the supremum of $\alpha$ such that $m_1 = \Omega(m_2^\alpha)$ is achievable; the two theorems give $\mathrm{crit}(\mathrm{C},\mathrm{bs}) = \mathrm{crit}(\mathrm{C},\mathrm{fbs}) = 2$ and $\mathrm{crit}(\mathrm{fbs},\mathrm{bs}) \ge 3/2$.