Random-indicator gadget
The inner gadget of \(f_{\mathrm{GSS}}\), on its own: $\mathrm{C}^0 = \Theta(n)$ with $\mathrm{bs}^0 = O(1)$.
total
arity: $n$ bits— also: the GSS inner function, indicator of a random code
Description
The indicator of $2^{n/50}$ points of the cube chosen uniformly at random. A random set that sparse is a good code -- its points are far apart, so no $0$-input has more than a constant number of disjoint sensitive blocks -- and yet it is dense enough that no small subcube avoids it, so every $0$-input needs a linear certificate.
Formal definition
Pick $x^1,\dots,x^N \in \{0,1\}^n$ uniformly at random with $N = 2^{n/50}$ and let $g_n$ be their indicator. With high probability [GSS16, Thm 32, Claim 34]:
- the points are at pairwise Hamming distance $\ge n/100$, so a $0$-input has at most $200$ disjoint sensitive blocks -- $\mathrm{bs}^0(g_n),\ \mathrm{fbs}^0(g_n) = O(1)$;
- every subcube of codimension $n/100$ contains one of the points, so no $0$-certificate is shorter than $n/100$ -- $\mathrm{C}^0(g_n)\ge n/100$.
The $1$-side is the opposite extreme: a $1$-input is an isolated point, so all $n$ of its bits are sensitive and its only certificate is the whole input.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Theta(n)\) | Floor $\mathrm{C}^0\ge n/100$ [GSS16, Thm 32]: a $0$-certificate is a subcube of $0$-inputs, and every subcube of codimension $n/100$ contains a planted point. Ceiling: the whole input, $n$. GSS16 |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\Theta(1)\) | Ceiling $\mathrm{bs}^0 = O(1)$ [GSS16, Thm 32]. A sensitive block $B$ at a $0$-input $x$ means $x^B$ is a planted point, so two disjoint blocks give two planted points at Hamming distance exactly $|B_1|+|B_2|$; pairwise distance $\ge n/100$ therefore forces every pair of blocks to have total size $\ge n/100$, and disjoint blocks fit in $n$ coordinates, so there are at most $201$ of them. Floor $1$: a neighbour of a planted point is a $0$-input with a sensitive bit. GSS16 |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\Theta(1)\) putative | Squeeze: $1\le\mathrm{s}^0\le\mathrm{bs}^0=O(1)$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(n\) putative | The $1$-inputs are isolated (pairwise distance $\ge n/100$), so any subcube containing one and no $0$-input is that single point. GSS16 |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(n\) putative | Every neighbour of an isolated planted point is a $0$-input. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(n\) putative | Squeeze: $\mathrm{s}^1\le\mathrm{bs}^1\le\mathrm{C}^1$, both $n$. |
| \(\mathrm{s}(f)\) Sensitivity | \(n\) | Squeeze: $\mathrm{s}=\max\{\mathrm{s}^0,\mathrm{s}^1\}=n$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(n\) | Squeeze: $\mathrm{s}\le\mathrm{bs}\le\mathrm{C}=n$. The whole gap between $\mathrm{C}^0$ and $\mathrm{bs}^0$ is invisible to the two-sided measures, which the $1$-side saturates. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(n\) | Squeeze: $\mathrm{bs}\le\mathrm{fbs}\le\mathrm{C}=n$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(n\) | Squeeze: $\mathrm{C}=\max\{\mathrm{C}^0,\mathrm{C}^1\}=n$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\Theta(n)\) putative | Floor: every $0$-input needs $n/100$ bits and every $1$-input needs $n$, so the minimum certificate complexity is already linear -- unusually, $\mathrm{C}_{\min}=\Theta(\mathrm{C})$ here. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n\) | Squeeze: $\mathrm{C}\le\mathrm{D}\le n$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(n\) | Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$, both $n$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(n)\) | Squeeze: $\mathrm{C}\le\mathrm{R}_0\le\mathrm{D}$. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n)\) | Squeeze: $\mathrm{R}=\Omega(\mathrm{fbs})=\Omega(n)$ and $\mathrm{R}\le\mathrm{D}=n$. Nothing about this gadget is easy for randomness; the point of it is the shape of the $0$-side, not a speed-up. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(n\) | Squeeze: $\mathrm{FC}=\mathrm{fbs}$ exactly. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{bs}=O(\mathrm{Q}^2)$ [BBCMdW01] with $\mathrm{bs}=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. 4 in total.
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{C}^0(f) = \Theta(n)\) against \(\mathrm{s}^0(f) = \Theta(1)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = \Theta(n)\) against \(\mathrm{bs}^0(f) = \Theta(1)\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^0(f_n) = O(1)\)from \(\mathrm{C}^0(f) = \Theta(n)\) against \(\mathrm{bs}^0(f) = \Theta(1)\)
-
\(\mathrm{C}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{C}_{\min}(f) = \Theta(n)\) against \(\mathrm{s}^0(f) = \Theta(1)\)
Separations it witnesses
-
$\mathrm{C}^0 = \Theta(n)$ while $\mathrm{bs}^0 = O(1)$: no bound of any kind holds in the other direction. The one-sided certificate complexity is not a function of the one-sided block sensitivity -- Nisan's $\mathrm{C}^0 \le \mathrm{s}^1\,\mathrm{bs}^0$ needs the $1$-side, and here it pays the full $\mathrm{s}^1 = n$.
Cited as a witness by
-
\(\mathrm{C}^0(g_n) = \Theta(n),\quad \mathrm{bs}^0(g_n) = O(1)\)
Notes
Recorded separately from \(f_{\mathrm{GSS}}\) because the two say different things. The composed $\mathrm{OR}_n\circ g_n$ multiplies the $0$-side by $n$ and so turns a constant $\mathrm{bs}^0$ into $\mathrm{bs}^0 = \Theta(n)$; that is what makes it a quadratic $\mathrm{C}$-vs-$\mathrm{bs}$ separation. The gadget on its own is the extreme case in a different direction: the ratio $\mathrm{C}^0/\mathrm{bs}^0$ is unbounded, which no amount of composition can improve on and which the composed function hides.
Not explicit: the construction is probabilistic, and the properties hold with high probability over the choice of the $N$ points. That is enough for a separation -- some choice works -- but the family has no description shorter than the list of points.