Q The Query Complexity Zoo
\(\mathrm{SINK}_m\)

Sink of a tournament

The function that killed the log-approximate-rank conjecture: spectral norm $O(\sqrt N)$, but $\mathrm{SINK}\circ\mathrm{XOR}$ has randomized communication complexity $\Omega(\sqrt N)$.

total separating arity: $N = \binom{m}{2}$ bits, one per edge of $K_m$, read as an orientation— also: SINK, the LARC function

Description

An input orients every edge of the complete graph $K_m$. Output $1$ iff some vertex is a sink -- every incident edge points into it.

A tournament has at most one sink, and that is the whole trick: the $m$ events "$v$ is a sink" are mutually exclusive, so the indicator is a sum of $m$ monomials rather than an OR of them, and the Fourier spectrum stays tiny.

Formal definition

$$\mathrm{SINK}_m(x) = \bigvee_{v=1}^{m}\ \bigwedge_{u \ne v} [\,u \to v\,], \qquad N = \binom m2.$$

Measure values

MeasureValueNotes
\(\deg(f)\) Exact degree \(m-1 = \Theta(\sqrt N)\) Exactly: $\mathrm{SINK}_m = \sum_{v}\prod_{u\ne v}[u\to v]$, a sum of $m$ disjoint monomials of degree $m-1$, and the top-degree terms do not cancel. CMS19
\(\hat{L}_1(f)\) Spectral norm \(O(m) = O(\sqrt N)\) Each of the $m$ disjoint conjunctions has spectral norm $1$ in the $\pm1$ normalisation, and spectral norm is subadditive. This -- a total function whose spectral norm is only $\sqrt N$ -- is what the refutation runs on. CMS19
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(m) = \Theta(\sqrt N)\) Upper: the standard candidate-elimination argument. Query $m-1$ edges to knock out all but one possible sink (a vertex with an out-edge is not a sink), then spend $m-1$ more verifying the survivor, so $\mathrm{D} \le 2m-3$. Lower: $\mathrm{D} \ge \deg = m-1$.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(m) = \Theta(\sqrt N)\) Take a tournament in which $k$ vertices have out-degree exactly $1$; each such vertex is one edge-flip from being a sink, and the flips are distinct edges, so $\mathrm{bs} \ge k$. Counting out-degrees, $k + (m-k)(m-1) \ge \binom m2$ allows $k = \Theta(m)$. Upper: $\mathrm{bs} \le \mathrm{D} = O(m)$.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}/3 \le \mathrm{R} \le \mathrm{D}$, with $\mathrm{bs} = \Theta(m)$ and $\mathrm{D} = O(m)$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(m-1\) To certify a sink you must exhibit all $m-1$ of its in-edges, and that suffices.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Omega(\sqrt m),\ O(m)\) Lower: $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(\sqrt m)$. Upper: $\widetilde{\deg} \le \deg = m-1$. I have not found the exact value stated anywhere; note that pinning it down would also pin $\mathrm{Q}$, which is likewise only known to $\Omega(\sqrt m)$ to $O(m)$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{fbs}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\chi(f)\) Conflict complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{CA}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(m),\ O(m^2)\) The sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23], which here reads $\max\{\Omega(m), \Theta(m)\} \le \mathrm{CG} \le m(m-1)$. It closes to $\Theta(m)$ exactly if $\mathrm{Adv} = \Theta(\sqrt m)$ and to $\Theta(m^2)$ if $\mathrm{Adv} = \Theta(m)$ -- the same open question as the \(\mathrm{Q}_{\varepsilon}(f)\) row of this entry. The old reading $\mathrm{CG} \le \mathrm{D}$ is not available: $\mathrm{CG}$ is not bounded by the arity. CGLMSG23
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(m) = \Theta(\sqrt N)\)· Sandwiched: $\mathrm{bs}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
\(\mathrm{s}^1(f)\) 1-sensitivity \(m-1\) Stated for $m \ge 5$. At a $1$-input the sink $v$ is unique, and flipping an edge not incident to $v$ leaves $v$ a sink, so only the $m-1$ edges at $v$ can be sensitive. Flipping $u \to v$ fails to be sensitive only if $u$ then becomes a sink, i.e. only if $u \to v$ was $u$'s only out-edge -- and at most one such $u$ can exist, since two of them would need an edge between them. So $\mathrm{s}^1 \in \{m-2, m-1\}$, and $m-1$ is attained by any $1$-input in which every non-sink has out-degree $\ge 2$ (e.g. a near-regular tournament on $V \setminus \{v\}$ with every vertex pointing at $v$), which exists for $m \ge 5$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(3\) Stated for $m \ge 3$. At a $0$-input, flipping the edge $e$ creates a sink iff $e$ is the unique out-edge of some vertex. Distinct vertices have distinct unique out-edges, so $\mathrm{s}^0_x$ counts the vertices of out-degree exactly $1$; if there are $k$ of them, the sub-tournament they span has $\binom k2$ edges and contributes $\binom k2$ to their out-degrees, whence $\binom k2 \le k$ and $k \le 3$. Three is attained: orient $u_1 \to u_2 \to u_3 \to u_1$ and every other edge into $\{u_1,u_2,u_3\}$. So $\mathrm{s}^0 = 3$ -- a constant, against $\mathrm{bs}^0 \ge m$ (the out-edge sets of the $m$ vertices are disjoint blocks, and flipping one makes its vertex a sink). SINK is thus a clean natural witness to a quadratic-and-then-some $\mathrm{s}^0$-versus-$\mathrm{bs}^0$ gap.
\(\mathrm{s}(f)\) Sensitivity \(m-1 = \Theta(\sqrt N)\) $\max\{\mathrm{s}^0,\mathrm{s}^1\} = \max\{3, m-1\}$.
\(\lambda(f)\) Spectral sensitivity \(\Theta(\sqrt m) = \Theta(N^{1/4})\) Pinned from both sides. Upper: the sensitivity graph is bipartite with side-degrees at most $\mathrm{s}^0$ and $\mathrm{s}^1$, so $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{3(m-1)}$. Lower: Huang's theorem in its spectral form gives $\lambda(f) \ge \sqrt{\deg(f)} = \sqrt{m-1}$. The two meet at $\Theta(\sqrt m)$. Note this is far below $\mathrm{s} = m-1$: SINK sits at the $\sqrt{\mathrm{s}}$ end of $\sqrt{\mathrm{s}} \le \lambda \le \mathrm{s}$, exactly like \(\mathrm{AND}_n\) and unlike \(\oplus_n\).
\(\mathrm{C}^0(f)\) 0-certificate complexity \(m\) putative To rule out every sink you must exhibit an out-edge for every vertex, and an oriented edge is an out-edge for exactly one of its endpoints -- so at least $m$ edges, and $m$ suffice (pick one out-edge per vertex; they are distinct). Note $\mathrm{C}^0 = m > m-1 = \mathrm{C}^1$, so the recorded $\mathrm{C} = \Theta(m)$ is exactly $m$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(m-1\) putative The cheapest inputs are the $1$-inputs, at $\mathrm{C}^1 = m-1$; every $0$-input costs $m$. So certificate complexity is essentially constant across SINK's domain, in sharp contrast to its sensitivity, which swings from $3$ to $m-1$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(m) = \Theta(\sqrt N)\) At least $m$: the out-edge sets of the $m$ vertices are disjoint, and flipping all of one vertex's out-edges makes it a sink. At most $\mathrm{bs} = O(m)$. This against $\mathrm{s}^0 = 3$ is the separation the $\mathrm{s}^0$ note describes.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\Theta(m) = \Theta(\sqrt N)\) Between $\mathrm{s}^1 = m-1$ and $\mathrm{bs} = O(m)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\deg/2 = (m-1)/2 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D} = O(m)$. Unlike the bounded-error $\mathrm{Q}$, which is open between $\Omega(\sqrt m)$ and $O(m)$, the exact value is pinned.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(N = \binom m2\) Every edge is relevant.
\(\deg_2(f)\) Mod-2 degree \(m-1 = \Theta(\sqrt N)\) putative Over $\mathbb{F}_2$ the same disjoint decomposition works: $\mathrm{SINK}_m = \sum_v \prod_{u\ne v}[u\to v]$, and each product is a degree-$(m-1)$ polynomial whose top monomial is the star at $v$ (an oriented edge variable is $x_e$ or $1+x_e$ mod $2$, so the top term is unaffected). The $m$ stars are distinct sets, so nothing cancels and $\deg_2 = \deg = m-1$. Confirmed exhaustively for $3 \le m \le 6$. SINK is therefore not a $\deg$-versus-$\deg_2$ separator, unlike \(\mathrm{IP}_n\).
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C} = \Theta(m)$ and $\mathrm{D} = O(m)$ here.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(m) = \Theta(\sqrt N)\) As for $\mathrm{UC}$: the leaves of any decision tree form a subcube partition, so $\mathrm{SP} \le \mathrm{D} = O(m)$, and $\mathrm{SP} \ge \mathrm{UC} \ge \mathrm{C} = \Theta(m)$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{C}_{\min} \le \mathrm{UC}_{\min} \le \mathrm{UC}$, with $\mathrm{C}_{\min} = m-1$ and $\mathrm{UC} = \Theta(m)$ here.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) Between $\mathrm{fbs}(f) = \mathrm{FC}(f) \le \mathrm{EC}(f)$ and $\mathrm{EC}(f) \le \mathrm{C}(f)$, both $\Theta(m)$ here.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: a Delayer who always defers survives $\mathrm{C}_{\min} = m-1$ rounds, and $\mathrm{rank} \le \mathrm{D} = O(m)$. Nothing about SINK is caterpillar-shaped.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(m)} = 2^{\Theta(\sqrt N)}\) Sandwiched: every leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = m-1$, so $\mathrm{DTsize} \ge 2^{m-1}$; and $\mathrm{DTsize} \le 2^{\mathrm{D}} = 2^{O(m)}$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(m) = \Theta(\sqrt N)\) putative Zero-error quantum buys nothing here. Fix the tournament on $V\setminus\{v\}$ to be a sink-free one (any cyclic orientation, $m \ge 4$) and leave the $m-1$ edges at $v$ free: the restriction is exactly $\mathrm{AND}_{m-1}$, and zero-error quantum search has no speedup at all, $\mathrm{Q}_0(\mathrm{AND}_{m-1}) = m-1$ [BCWZ99]. Restrictions only decrease $\mathrm{Q}_0$, so $\mathrm{Q}_0 \ge m-1$; and $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = O(m)$. Note this pins $\mathrm{Q}_0$ even though the bounded-error $\mathrm{Q}$ is open between $\Omega(\sqrt m)$ and $O(m)$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(m^2) = \Theta(N)\) putative Non-adaptively you must read essentially the whole tournament, a full quadratic above $\mathrm{R} = \Theta(\sqrt N)$. Hard distribution: pick $v$ and $u \ne v$ uniformly, orient every edge into $v$ and the rest of the tournament uniformly at random, then flip the edge $uv$ with probability $1/2$. Flipping it destroys the sink and creates a new one only if $u$ is a sink of the sub-tournament, which happens with probability $2^{-(m-2)}$. The unordered pair $\{u,v\}$ is uniform over all $\binom m2$ edges, and flipping the coin is an involution that leaves $x|_S$ unchanged whenever $uv \notin S$, so any fixed $S$ errs with probability $\ge \tfrac12(1 - |S|/\binom m2) - 2^{-(m-2)}$. Hence $|S| = \Omega(N)$, and $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(m^2 2^{-m})\) putative Exactly $\binom m2 2^{3-m}\big(1 - 2^{2-m}\big)$. Every sensitive hypercube edge has a $1$-endpoint, so $\mathrm{I}(f) = 2^{1-N}\sum_{f(x)=1}\mathrm{s}(x)$. At a $1$-input the sink $v$ is unique and only its own $m-1$ edges can matter; flipping $uv$ kills $v$ and creates a sink only if $u$ already loses to all of $V\setminus\{u,v\}$, and at most one such $u$ exists. Counting: $m\,2^{\binom{m-1}2}$ inputs have a sink and $m(m-1)2^{\binom{m-2}2}$ of them also have such a $u$. Verified exhaustively for $m \le 7$. So average sensitivity is exponentially small, while $\mathrm{s} = m-1$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Omega(\sqrt m),\ O(m)\) Open, and the same gap as $\widetilde{\deg}$. Lower: $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt{\mathrm{bs}}) = \Omega(\sqrt m) = \Omega(N^{1/4})$. Upper: $\mathrm{Q} \le \mathrm{D} = O(m)$, and the obvious quantum algorithm does no better -- amplitude amplification over the $m$ candidate sinks, each checked by a Grover search for an out-edge, costs $O(\sqrt m \cdot \sqrt m) = O(m)$, exactly what candidate elimination already gives classically. The at-most-one-sink promise is what blocks the usual $\mathrm{OR}\circ\mathrm{AND}$ adversary bound of $\Omega(m)$, so neither end is known to be tight.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Omega(\sqrt m),\ O(m)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}$ is open between $\Omega(\sqrt m)$ and $O(m)$ here. Pinning this SDP down would settle $\mathrm{Q}(\mathrm{SINK})$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Omega(\sqrt m),\ O(m)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)); see \(\mathrm{Adv}^{\pm}(f)\).
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Omega(\sqrt m),\ O(m)\) Sandwiched between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}$, which are $\Theta$ of each other and open in the same range here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Omega(\sqrt m),\ O(m)\) Lower: $\lambda(f) \le \mathrm{Adv}(f)$ with $\lambda = \Theta(\sqrt m)$. Upper: $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{m(m-1)} = \Theta(m)$, the certificate barrier, which here coincides with $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = O(m)$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(m) = \Theta(\sqrt N)\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)).
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(m) = \Theta(\sqrt N)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(m) = \Theta(\sqrt N)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(m)$. Yao77
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m)$ meets $\mathrm{R} = \Theta(m)$.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(m) = \Theta(\sqrt N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)). CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(m) = \Theta(\sqrt N)\) The same non-signaling collapse; see \(\mathrm{CG}^{*}(f)\). CGLMSG23
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt m) = \Theta(N^{1/4})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m)$ here. It coincides with $\lambda$ and with the lower end of the $\mathrm{Q}$ range. Aaronson08
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(m),\ O(m\log m)\) Between $\mathrm{R} = \Theta(m)$ and $O(\mathrm{R}\log \mathrm{R})$. The influence-based lower bound $\mathrm{N}_p = \Omega(\mathrm{I}\log \mathrm{I})$ [GLX26noisy] gives nothing, $\mathrm{I}$ being exponentially small.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(\sqrt m),\ O(m\log m)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$, and $\mathrm{Q}$ is itself open here; the upper end also follows from $\mathrm{Q}^{\mathrm{rob}} \le \mathrm{N}_p = O(m\log m)$.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(m-1 = \Theta(\sqrt N)\) putative Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = m-1$. Lower: fix a sink-free tournament on $V \setminus \{v\}$ and leave the $m-1$ edges at $v$ free; the restriction is $\mathrm{AND}_{m-1}$, whose nondeterministic degree is $m-1$ (a polynomial nonzero exactly at $1^k$ is a multiple of $\prod_i x_i$), and restrictions do not increase $\mathrm{ndeg}$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\lceil (m-1)/2 \rceil = \Theta(\sqrt N)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf03], and $\mathrm{ndeg} = m-1$ here. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(m) = \Theta(\sqrt N)\) putative Sandwiched: $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \ge m-1$, and $\mathrm{rdeg}(f) \le \mathrm{C}(f) = m$. (For the record the complement is no harder: at most one vertex is a sink, so $\overline{\mathrm{SINK}} = 1 - \sum_v \prod_{u\ne v}[u\to v]$ on the nose, giving $\mathrm{ndeg}(\bar f) \le m-1$ as well.)
\(\deg_p(f)\) Mod-p degree \(m-1 = \Theta(\sqrt N)\) putative For every prime $p$, by the same disjoint decomposition that gives $\deg$ and $\deg_2$: the $m$ star monomials are distinct sets and each carries coefficient $\pm1$ over $\mathbb{Z}$, so nothing cancels in any characteristic.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(m) = \Theta(\sqrt N)\) putative Lower: $\mathrm{spar}(f) \le 4^{\mathrm{D}^{\oplus}(f)}$ with $\mathrm{spar} = \Theta(m2^m)$ gives $\mathrm{D}^{\oplus} \ge (m-1)/2$. Upper: $\mathrm{D}^{\oplus} \le \mathrm{D} = O(m)$. Parity queries buy nothing, which is the query-level shadow of the [CMS19] refutation: $\mathrm{SINK}$ has tiny spectral norm yet its parity decision trees are as deep as its ordinary ones.
\(\mathrm{spar}(f)\) Fourier sparsity \(m2^{m-1} - m^2 + 1 = \Theta(m2^{m})\) putative A set $S$ has $\hat F(S) \ne 0$ iff $|S| \ge 2$ and $S$ lies inside some star (each star has $2^{m-1}-m$ such subsets, and no two stars share one), plus the empty set. Singletons cancel exactly: the edge $uv$ appears in the star at $v$ with the opposite sign to the star at $u$. Verified exhaustively for $m = 3,4,5$ (the empty coefficient also vanishes at $m = 4$, where $\mathrm{SINK}_4$ happens to be balanced, so the count is one lower there). Note $\log_2\mathrm{spar} = \Theta(m) = \Theta(\mathrm{D})$ while $\mathrm{L}_1 = O(m)$ -- sparse and of small spectral norm.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(\binom m2 = N\) putative Full, for $m \ge 4$. The support contains every pair of edges sharing a vertex, and those pairs already span all even-weight sets; it also contains $3$-subsets of a star once $m \ge 4$, so the span is all of $\mathbb{F}_2^{N}$. Verified exhaustively at $m = 4,5$. The Fourier-dimension bound $\mathrm{D}^{\oplus} \le \dim_{\mathbb{F}_2}$ is therefore vacuous here, and the real $\mathrm{D}^{\oplus} = \Theta(\sqrt N)$ comes from sparsity instead.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(m^2 2^{-m})\) For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f)$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\Theta(2^{-m})\) putative Relabelling vertices acts transitively on edges, so every coordinate has the same influence and $\mathrm{MaxInf} = \mathrm{I}(f)/N = 2^{3-m}(1-2^{2-m})$.
\(\mathrm{Var}(f)\) Variance \((1+o(1))\,m\,2^{3-m}\) $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry, i.e. $4p(1-p)$ at $p = m2^{1-m}$: a random tournament almost never has a sink.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(m) = \Theta(\sqrt N)\) putative $\Theta(m2^{-m})$ over $\Theta(2^{-m})$. Tight: $\mathrm{D} = \mathrm{R}_0 = \Theta(m)$, so OSSS recovers the true complexity of SINK up to a constant -- one of only two functions in the zoo where it does.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(m) = \Theta(\sqrt N)\) putative The sink survives $\delta$-noise exactly when none of its $m-1$ in-edges flips, so $\mathrm{NS}_\delta$ crosses $\mathrm{Var}/4$ at $(1-\delta)^{m-1} = \tfrac12$ and $\delta^{*} = \Theta(1/m)$. Also tight against $\mathrm{D} = \Theta(m)$.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \((1+o(1))\,m\,2^{2-m}\big(1-(1-\delta)^{m-1}\big)\) putative A random tournament has a sink with probability $m2^{1-m}$, and the sink survives $\delta$-noise exactly when none of its $m-1$ in-edges flips; a new sink appearing needs $\ge m-2$ simultaneous flips and is lower order. So $\mathrm{NS}_\delta = 2\Pr[f(x)=1]\big(1-(1-\delta)^{m-1}\big)(1+o(1))$. Consistency check: as $\delta \to 0$ this is $\delta\,m(m-1)2^{2-m} = \delta\,\mathrm{I}(f)$ exactly.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - m2^{3-m}\big(1-(\tfrac{1+\rho}{2})^{m-1}\big)\) putative Substituting $\delta = (1-\rho)/2$ into $\mathrm{NS}$ above, via $\mathrm{Stab}_\rho = 1 - 2\mathrm{NS}_\delta$. SINK is almost perfectly noise-stable simply because it is almost always $0$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(m) = \Theta(\sqrt N)\) putative The zoo's shortcut $\mathrm{R} = \Theta(n) \Rightarrow \mathrm{noisyR} = \Theta(\mathrm{R})$ does not apply -- $\mathrm{R} = \Theta(\sqrt N)$ here, not linear in the arity -- so the lower bound has to come from a restriction. Fix the tournament on $\{2,\dots,m\}$ to be transitive and orient $\{1,m\}$ into vertex $1$: then every vertex except $1$ has an outgoing edge, and the function of the $m-2$ free edges $\{1,u\}$ is exactly $\mathrm{AND}_{m-2}$. Noisy randomized complexity is monotone under restriction, and $\mathrm{noisyR}(\mathrm{AND}_k) = \Theta(k)$ since $\mathrm{R}(\mathrm{AND}_k) = k$ is linear in its arity. Upper: $\mathrm{noisyR} \le \mathrm{R} = \Theta(m)$ (\(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(m) = \Theta(\sqrt N)\) putative Product distributions lose nothing here. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m)$. Lower, by the same $\mathrm{AND}_{m-2}$ restriction as \(\mathrm{noisyR}(f)\) -- restricting is legal because a product distribution on the free variables extends to a product distribution with point masses on the fixed ones -- together with $\mathrm{D}^{\mathrm{prod}}(\mathrm{AND}_k) = \Theta(k)$: take each bit $1$ independently with probability $1-1/k$, so that after $d$ observed ones the conditional probability of $\mathrm{AND} = 1$ is $(1-1/k)^{k-d}$, which stays in $[e^{-1}, e^{-1/2}]$ until $d \ge k/2$ and therefore keeps the error above $1/3$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(\sqrt m),\ O(m)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$ (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{cjdeg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg} \in [\Omega(\sqrt m), O(m)]$ and $\mathrm{R} = \Theta(m)$. The window is exactly the open window on $\widetilde{\deg}$ -- pinning the approximate degree of SINK would pin this too.

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. 13 in total.

Separations it witnesses

Cited as a witness by

Notes

What is actually refuted. The log-approximate-rank conjecture (Lee-Shraibman) said $\mathrm{R}^{cc}(F) \le \mathrm{polylog}(\text{approximate rank of } F)$ for total $F$. [CMS19] take $F = \mathrm{SINK}_m \circ \mathrm{XOR}$: its approximate rank is $2^{O(\log m)}$-ish because the spectral norm is $O(m)$, while a corruption argument (lifting a randomized parity-decision-tree bound, via Shearer's lemma) gives $\mathrm{R}^{cc} = \Omega(m)$. The same function refutes Grolmusz's conjecture and the parity-measure conjecture of Tsang-Wong-Xie-Zhang, which had implied the log-rank conjecture for XOR functions.

The quantum version of the conjecture fell the same year, independently: [SinhadeWolf19] and [ABT19].

Why composed functions had not done this before. For query complexity the decision-tree analogue of the log-rank conjecture is true for both exact and approximate degree, so a $g \circ \mathrm{XOR}$ counterexample has to come from a $g$ whose ordinary Fourier structure is simple but whose parity decision trees are not. SINK is exactly that.