Q The Query Complexity Zoo
\(f_{\mathrm{GSS}}\)

Gilmer-Saks-Srinivasan functions

Separates C from RC quadratically -- with no log loss -- and RC from bs by a $3/2$ power.

total separating 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

MeasureValueNotes
\(\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.

… and 42 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

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$.