Q The Query Complexity Zoo
\(g_n\)

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

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

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

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.