Scorpion graphs
The nontrivial graph property that is nowhere near evasive: $\mathrm{D} = \Theta(m) = \Theta(\sqrt N)$ out of $N$ possible queries.
total basic arity: $N = \binom{m}{2}$ bits, the adjacency matrix of an $m$-vertex graph
Description
A graph is a scorpion if it has three special vertices -- a sting $s$ of degree $1$, adjacent only to the tail $t$; a tail $t$ of degree $2$, adjacent only to $s$ and to the body $b$; and a body $b$ adjacent to every vertex except $s$. The remaining $m-3$ vertices (the "feet") may be joined arbitrarily.
"Is this graph a scorpion?" is a graph property -- invariant under relabelling vertices -- and it is nontrivial. It is also decidable in $O(m)$ queries.
Formal definition
The property $P = \{G : \exists\, s,t,b \text{ with } N(s) = \{t\},\ N(t) = \{s,b\},\ N(b) = V \setminus \{s\}\}$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(m) = \Theta(\sqrt N)\) | Upper: at most $6m$ queries. Walk a candidate body around, maintaining a set of vertices known not to be the body; each query eliminates a vertex, so $O(m)$ queries identify $b$ or reject, and $2(m-1)$ more check $s$ and $t$. Lower: $\Omega(m)$, since the answer depends on all $m$ vertices. BvEBL74 LovaszYoung02 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(m)\) | Between $\Omega(\sqrt{\mathrm{bs}})$ and $\mathrm{D} = O(m)$; nothing below $\Theta(m)$ is possible because the property depends on every vertex. |
| \(\deg(f)\) Exact degree | \(3m-6 = \Theta(\sqrt N)\) putative | Exactly, for $m \ge 5$. For $m \ge 5$ a scorpion has a unique triple $(s,t,b)$ -- the body is the only vertex of degree $m-2$, since a foot misses both $s$ and $t$ -- so $\mathrm{SCORP}_m = \sum_{(s,t,b)} \mathbf{1}[\text{the } 3m-6 \text{ pairs touching } \{s,t,b\} \text{ take their scorpion values}]$ is a sum of disjoint subcube indicators of codimension $3m-6$. Hence $\deg \le 3m-6$. It is attained: all six orderings of one $3$-set share the same touch set $T$ and each contributes $(-1)^{2m-5} = -1$ to the coefficient of $\prod_{e\in T} x_e$, so that coefficient is $-6 \ne 0$. Confirmed exhaustively for $m \le 6$. Note $\deg = \mathrm{s}^1 = \mathrm{C}^1$, all three equal to $3m-6$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\deg/2 = (3m-6)/2 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D} = O(m)$. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(m) = \Theta(\sqrt N)\) putative | Zero-error quantum buys nothing. Fix the triple $(s,t,b) = (1,2,3)$, make the feet pairwise non-adjacent, fix all touch pairs at their scorpion values except the $m-3$ body-foot pairs, and leave those free: for $m \ge 6$ the result is a scorpion iff all $m-3$ are present (no foot can take over as body, its degree being at most $1$), so the restriction is $\mathrm{AND}_{m-3}$. Zero-error quantum search has no speedup at all, $\mathrm{Q}_0(\mathrm{AND}_k) = k$ [BCWZ99], and restrictions only decrease $\mathrm{Q}_0$, so $\mathrm{Q}_0 \ge m-3$; and $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} = O(m)$. BCWZ99 |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(m)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R} = \Theta(m)$ and $\mathrm{D} = O(m)$ here. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Omega(\sqrt m),\ O(m)\) | Lower: the restriction above turns $\mathrm{SCORP}_m$ into $\mathrm{AND}_{m-3}$, so $\widetilde{\deg} \ge \widetilde{\deg}(\mathrm{AND}_{m-3}) = \Theta(\sqrt m)$. Upper: $\widetilde{\deg} \le \deg = 3m-6$. Not pinned down here; as with \(\mathrm{SINK}_m\), settling it would also settle $\mathrm{Q}$. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(O(m)\) | From $\mathrm{Q} \le \mathrm{D}$. No better bound is recorded, and no better one is obviously available: this is not a search problem. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(m)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and $\mathrm{R}_{\varepsilon}(f) = \Theta(m)$ here. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(3m-6\) putative | Take the scorpion with independent feet. The pairs touching $\{s,t,b\}$ number $3 + 3(m-3) = 3m-6$, and each of them is sensitive: adding an edge at the sting or the tail destroys the only degree-$1$/degree-$2$ pair, deleting $st$ or $tb$ breaks the chain, and deleting a body-foot edge stops $b$ from dominating -- in every case no other triple can take over, because a replacement sting would need a neighbour of degree $2$ and the only such vertex is gone. Pairs between feet are insensitive by definition. Exhaustive search confirms $\mathrm{s}^1 = 3m-6$ exactly for $m \le 7$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(2m-4\) putative | The extremal $0$-input is $K_{m-2} \sqcup K_2$: a clique on $A$, plus a lone edge $\{u,v\}$ with no edges to $A$. Adding $ua$ for any $a \in A$ makes a scorpion with sting $v$, tail $u$, body $a$ (the clique makes $a$ dominate everything but $v$); symmetrically for $va$. That is $2(m-2)$ sensitive pairs, and exhaustive search confirms $\mathrm{s}^0 = 2m-4$ exactly for $m \le 7$. Contrast $\mathrm{s}^1 = 3m-6$: the scorpion is mildly $1$-biased. |
| \(\mathrm{s}(f)\) Sensitivity | \(3m-6\) putative | $\max(\mathrm{s}^0,\mathrm{s}^1) = \max(2m-4,\,3m-6)$. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(3m-6\) putative | The $3m-6$ touch pairs of a triple $(s,t,b)$ are a certificate: they pin $N(s)=\{t\}$, $N(t)=\{s,b\}$ and $N(b) = V\setminus\{s\}$, and the feet may then do anything. So $3m-6 = \mathrm{s}^1 \le \mathrm{bs}^1 \le \mathrm{C}^1 \le 3m-6$ and all three coincide -- the scorpion is $1$-certificate-tight, verified by brute force for $m \le 9$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(3m-6\) putative | Squeezed between $\mathrm{s}^1$ and $\mathrm{C}^1$, both $3m-6$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Theta(m)\) putative | Upper: $\mathrm{C}^0 \le \mathrm{D} = O(m)$. Lower: at the empty graph, refuting the triple $(\sigma,\tau,\beta)$ needs a queried edge in $\{\sigma\tau\} \cup \mathrm{star}(\beta)\setminus\{\beta\sigma\}$, so a $0$-certificate is a hitting set for that family; unless $P$ meets $\mathrm{star}(\beta)$ twice for nearly every $\beta$ it must contain a near-clique, and $\sum_\beta |P \cap \mathrm{star}(\beta)| = 2|P|$ then forces $|P| = \Omega(m)$; the empty graph's own optimum is exactly $m-1$ (a single star of absent pairs, isolating a vertex) for $5 \le m \le 8$, and that is where $\mathrm{C}_{\min}$ comes from. The maximum over $0$-inputs is larger: exhaustive search gives $\mathrm{C}^0 = 2m-4$ for $4 \le m \le 6$, matching $\mathrm{s}^0$ exactly, so $\mathrm{s}^0 = \mathrm{bs}^0 = \mathrm{C}^0$ and the extremal $0$-input is $K_{m-2}\sqcup K_2$ in all three. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\Theta(m)\) | Squeezed between $\mathrm{s}^0 = 2m-4$ and $\mathrm{C}^0 = \Theta(m)$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\Theta(m)\) | Squeezed between $\mathrm{s} = 3m-6$ and $\mathrm{C} = \Theta(m)$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\Theta(m)\) | Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, both $\Theta(m)$. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(m)\) putative | $\max(\mathrm{C}^0,\mathrm{C}^1)$; also directly $\mathrm{C} \le \mathrm{D} = O(m)$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\binom{m}{2} = N\) putative | Every pair $uv$ is sensitive somewhere -- take the scorpion with sting $u$, tail $v$ -- so a fixed query set that omits $uv$ fails to separate that scorpion from its neighbour. Hence all $N$ bits must be read in advance, against $\mathrm{D} = \Theta(\sqrt N)$. (The $\mathrm{D}^{\mathrm{na}} = N$ half is the generic fact that a non-adaptive algorithm must read every relevant variable; what is special here is how small $\mathrm{D}$ is.) \(\mathrm{Nav}_k\) pushes the same phenomenon to an exponential gap; the scorpion is the natural graph-theoretic instance. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(m-1\) putative | Upper: at the empty graph, fixing the $m-1$ pairs at one vertex to absent isolates it, and a scorpion has no isolated vertex (the body dominates everything but the sting, and the sting has degree $1$). Lower: if a set $S$ of $|S| = k$ pairs leaves three vertices untouched, take them as $(s,t,b)$ -- every pair the triple touches is then free, and the feet may do anything -- so the subcube contains a scorpion and $S$ is not a $0$-certificate; hence $m - 2k \le 2$, i.e. every $0$-input costs at least $(m-2)/2$. Every $1$-input costs $\mathrm{C}^1 = 3m-6$. Exhaustive search gives $\mathrm{C}_{\min} = m-1$ exactly for $4 \le m \le 6$, attained only at graphs with an isolated vertex. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: a Delayer who always defers survives $\mathrm{C}_{\min} = m-1$ rounds, so $\mathrm{rank} \ge m-1$, and $\mathrm{rank} \le \mathrm{D} = O(m)$. So the scorpion decision tree is genuinely branching, not a caterpillar -- unlike \(\mathrm{OR}_n\), whose $\mathrm{D}$ is also large while $\mathrm{rank} = 1$. |
| \(\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)}$. Note $\log_2\mathrm{DTsize} = \Theta(\sqrt N)$ while there are $N$ variables -- the tree is exponentially smaller than the truth table. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(\Theta(m)\) | 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)\) | The leaves of the $O(m)$-query algorithm form a monochromatic 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)\) | 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)\) | Between $\mathrm{fbs}(f) = \mathrm{FC}(f) \le \mathrm{EC}(f)$ and $\mathrm{EC}(f) \le \mathrm{C}(f)$, both $\Theta(m)$ here. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\Theta(m)\) | $\mathrm{FC} = \mathrm{fbs}$ exactly, by LP duality, and $\mathrm{fbs} = \Theta(m)$ here. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(m)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m)$ here. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(m^2) = \Theta(N)\) putative | Non-adaptively the scorpion property is evasive up to a constant, a full quadratic above $\mathrm{R} = \Theta(\sqrt N)$. Hard distribution: draw an ordered triple $(s,t,b)$ uniformly and the foot subgraph uniformly, giving a scorpion $G$, then delete the edge $st$ with probability $\tfrac12$ (which isolates $s$, so the result is never a scorpion). Flipping that coin is a measure-preserving involution that does not change $x|_S$ whenever $st \notin S$, so given $x|_S$ the answer is an unbiased coin on that event; since $\{s,t\}$ is uniform over all $\binom m2$ pairs, a fixed $S$ succeeds with probability at most $1 - \tfrac12(1 - |S|/\binom m2)$, forcing $|S| \ge \binom m2/3$. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \(\Theta(m^4 2^{-3m}) = 2^{-\Theta(\sqrt N)}\) putative | Exactly $\mathrm{I} = 6m(m-1)(m-2)^2\,2^{6-3m}$ for $m \ge 5$. Every scorpion has sensitivity exactly $3m-6$ (the proof of $\mathrm{s}^1$ applies to every scorpion, not just the one with independent feet), so the sensitivity graph has $m(m-1)(m-2)2^{\binom{m-3}2}(3m-6)$ edges; divide by $2^{\binom m2}$ and double. Verified exactly against exhaustive computation for $5 \le m \le 7$. The scorpion property is thus vanishingly rare and vanishingly influential, which is why $\mathrm{R}$ cannot be beaten below $\Theta(m)$ by sampling. |
| \(\lambda(f)\) Spectral sensitivity | \(\Omega(\sqrt m),\ O(m)\) | Lower: Huang's theorem in spectral form, $\lambda \ge \sqrt{\deg} = \sqrt{3m-6}$. Upper: the sensitivity graph is bipartite with side-degrees $\mathrm{s}^1 = 3m-6$ and $\mathrm{s}^0 = 2m-4$, so $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt6\,(m-2)$. Not pinned; exhaustive computation gives $\lambda^2 = 16,\,23,\,26,\,33$ at $m = 4,\dots,7$, which tracks the $\Theta(\sqrt m)$ end. |
| \(\hat{L}_1(f)\) Spectral norm | \(O(m^3) = O(N^{3/2})\) putative | For $m \ge 5$ the property is a disjoint union of $m(m-1)(m-2)$ subcubes, one per ordered triple, and the indicator of a subcube has spectral norm $1$; spectral norm is subadditive, so the $\pm1$ version has $\hat{\mathrm{L}}_1 \le 1 + 2m(m-1)(m-2)$. Like \(\mathrm{SINK}_m\), the scorpion is a total function whose spectral norm is only polynomial in $N$, against the $2^{\Theta(N)}$ of a generic function. The exhaustive values $16.5,\,40.6,\,99.1$ at $m = 5,6,7$ leave the constant, and indeed the exponent, unsettled. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(\Theta(m)\) | For a Boolean function the solution to be produced is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = \Theta(m)$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(m)\) | 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)\)); here $\mathrm{R} = \Theta(m)$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(m)\) | Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(m)$. Yao77 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(m)\) | Sandwiched between $\mathrm{R} = \Theta(m)$ and $\mathrm{R}_0 = \Theta(m)$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(m)\) | 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)$. So the scorpion composes perfectly: $\mathrm{R}(\mathrm{SCORP}_m \circ g^N) = \Omega(m\,\mathrm{R}(g))$. |
| \(\chi(f)\) Conflict complexity | \(\Theta(m)\) | Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) \lesssim \mathrm{RS}(f)$, with $\mathrm{bs} = \Theta(m)$ and $\mathrm{RS} = \Theta(m)$ here. The whole inner-measure chain $\chi \lesssim \mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$ collapses to $\Theta(m)$ on this function. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(m)\) | Squeezed inside the chain $\mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$, with $\mathrm{RS} = \Theta(m)$ and $\mathrm{R} = \Theta(m)$. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(m)\) | Squeezed between $\bar\chi = \Theta(m)$ and $\mathrm{R} = \Theta(m)$. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(m)\) | Squeezed between $\mathrm{LR} = \Theta(m)$ and $\mathrm{R} = \Theta(m)$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(m)\) | $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ [ABIKPS17], and $\mathrm{fbs} = \Theta(m)$ here. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(m)\) | $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CG}^{*}) = \Theta(\mathrm{CG}^{\mathrm{ns}}) = \Theta(\mathrm{CA})$, the non-signaling bottleneck [CGLMSG23], and $\mathrm{CA} = \Theta(m)$ here. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(m)\) | Entanglement buys nothing beyond the non-signaling value: $\mathrm{CG}^{*} = \Theta(\mathrm{CA}) = \Theta(m)$. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(m)\) | The non-signaling relaxation is already $\Theta(\mathrm{CA}) = \Theta(m)$. CGLMSG23 |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Omega(m),\ O(m^2)\) | The sandwich is $\max\{\mathrm{Adv}^2, \mathrm{R}_0, \mathrm{CA}\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]: here $\mathrm{R}_0 = \Theta(m)$ from below and $\mathrm{C}^0\mathrm{C}^1 = \Theta(m)\cdot(3m-6) = \Theta(m^2)$ from above, and $\mathrm{Adv}$ is itself only pinned to $[\Omega(\sqrt m), O(m)]$. Note the direction: $\mathrm{R}_0 = O(\mathrm{CG})$, not the reverse -- private coin is the one variant of the game that is harder than zero-error query complexity, and is not capped by $\mathrm{D}$. CGLMSG23 |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(m)\) | Sandwiched: $\mathrm{RC}(f) \le \mathrm{prt}(f) + O(1) \le 2\,\mathrm{R}(f) + O(1)$, with $\mathrm{RC} = \Theta(m)$ and $\mathrm{R} = \Theta(m)$ here. The LP loses nothing on the scorpion, in contrast with the quadratic loss it can suffer in general. JainKlauck10 |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(\binom{m}{2} = N\) putative | Full. The Fourier support fails to span $\mathbb{F}_2^N$ exactly when $f(x \oplus a) = f(x)$ for some $a \ne 0$, since the shifted function has coefficients $(-1)^{a \cdot S}\hat f(S)$; no nonempty edge set $a$ can be flipped without ever destroying scorpionhood (flip an edge of $a$ at the sting of a scorpion whose triple avoids the rest of $a$). Confirmed by exhaustive computation for $m \le 7$. So a parity decision tree gets no help from a global change of basis, even though $\mathrm{D} = \Theta(\sqrt N)$. |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \(\Theta(m^4 2^{-3m})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f) = 6m(m-1)(m-2)^2\,2^{6-3m}$; see \(\mathrm{I}(f)\). |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(12(m-2)^2\,2^{6-3m}\) putative | The property is invariant under relabelling vertices and the symmetric group is transitive on pairs, so every coordinate has the same influence and $\mathrm{MaxInf} = \mathrm{I}(f)/N = 6m(m-1)(m-2)^2 2^{6-3m}/\binom m2 = \Theta(m^2 2^{-3m})$. |
| \(\mathrm{Var}(f)\) Variance | \((4+o(1))\,m(m-1)(m-2)\,2^{6-3m} = \Theta(m^3 2^{-3m})\) | $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry: a uniform graph is a scorpion with probability $p = m(m-1)(m-2)2^{6-3m}$ and $\mathrm{Var} = 4p(1-p)$. |
| \(\mathrm{osss}(f)\) OSSS number | \((1+o(1))\,m/3\) putative | Exactly $4m(m-1)(m-2)2^{6-3m}$ over $\mathrm{MaxInf} = 12(m-2)^2 2^{6-3m}$, i.e. $m(m-1)/(3(m-2))$. Tight: $\mathrm{D} = \mathrm{R}_0 = \Theta(m)$, so this is the witness recorded for \(\mathrm{osss}(f)\) vs \(\mathrm{R}_{0}(f)\) -- the exponent-$1$ lower bound on the OSSS inequality itself. |
| \(\mathrm{nsr}(f)\) Noise robustness | \(\Theta(m)\) putative | A scorpion is destroyed when one of the $3m-6$ pinned adjacencies flips, so $\mathrm{NS}_\delta$ crosses $\mathrm{Var}/4$ at $(1-\delta)^{3m-6} = \tfrac12$ and $\delta^{*} = \Theta(1/m)$. Tight: equal to $\mathrm{s} = 3m-6$ up to constants, so this is the witness for \(\mathrm{nsr}(f)\) vs \(\mathrm{s}(f)\), and equal to $\mathrm{D} = \Theta(m)$ as well. |
| \(\mathrm{NS}_{\delta}(f)\) Noise sensitivity | \((2+o(1))\,m(m-1)(m-2)\,2^{6-3m}\big(1-(1-\delta)^{3m-6}\big)\) putative | Noise sensitivity is $2\Pr[f(x)=1,\,f(y)=0]$. A uniform graph is a scorpion with probability $p = m(m-1)(m-2)2^{6-3m}$, and given a scorpion with triple $(s,t,b)$ the noisy copy stays a scorpion essentially only if none of the $3m-6$ touch pairs flips -- acquiring a different triple needs $\Omega(m)$ flips and costs a further $2^{-\Omega(m)}$ -- whence the displayed formula. Consistency: as $\delta \to 0$ it tends to $6m(m-1)(m-2)^2 2^{6-3m}\,\delta = \delta\,\mathrm{I}(f)$, exactly the recorded \(\mathrm{I}(f)\). |
| \(\mathrm{Stab}_{\rho}(f)\) Noise stability | \(1 - (4+o(1))\,m(m-1)(m-2)\,2^{6-3m}\big(1-(\tfrac{1+\rho}{2})^{3m-6}\big)\) putative | From $\mathrm{Stab}_{\rho} = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. Stability is $1 - 2^{-\Theta(m)}$ for every fixed $\rho < 1$: the $\pm1$ version of the scorpion property is a constant function up to an exponentially small correction, which is the Fourier shadow of $\mathrm{I}(f) = 2^{-\Theta(\sqrt N)}$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(m) = \Theta(\sqrt N)\) putative | As on \(\mathrm{SINK}_m\), the "$\mathrm{R}$ linear in the arity" shortcut is unavailable ($\mathrm{R} = \Theta(\sqrt N)$), so the lower bound comes from a restriction to $\mathrm{AND}$. Put the sting at $1$, the tail at $2$ and the body at $3$: fix $\{1,2\}$ and $\{2,3\}$ present, every other edge at $1$ or $2$ absent, and every foot-foot edge absent. What remains free is the $m-3$ edges $\{3,u\}$, $u \ge 4$, and the graph is a scorpion iff all of them are present -- no other vertex can play body, since the feet now have degree $\le 1$. So $\mathrm{noisyR} \ge \mathrm{noisyR}(\mathrm{AND}_{m-3}) = \Theta(m)$, and $\mathrm{noisyR} \le \mathrm{R} = \Theta(m)$. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(\Theta(m) = \Theta(\sqrt N)\) putative | The same $\mathrm{AND}_{m-3}$ restriction as \(\mathrm{noisyR}(f)\), with $\mathrm{D}^{\mathrm{prod}}(\mathrm{AND}_k) = \Theta(k)$ (each bit $1$ independently with probability $1-1/k$; see the \(\mathrm{SINK}_m\) entry), against the ceiling $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m)$. Note the contrast with $\mathrm{D}$: the scorpion property is $\Theta(m)$-easy deterministically too, so unlike \(\mathrm{CONN}_m\) there is nothing for randomness or for a product distribution to exploit. |
| \(\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)$, with $\widetilde{\deg} \in [\Omega(\sqrt m), O(m)]$ and $\mathrm{R} = \Theta(m)$; the window is inherited wholesale from the open window on $\widetilde{\deg}$. |
| \(\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. So a quantum verifier checks the scorpion property with a quadratically shorter certificate than the classical $\mathrm{C} = \Theta(m)$. Aaronson08 |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Omega(m),\ O(m\log m)\) | Generic: $\mathrm{R}(f) \le \mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ [FRPU94], with $\mathrm{R} = \Theta(m)$. The $\mathrm{I}\log \mathrm{I}$ lower bound is useless here, the scorpion's total influence being exponentially small. FRPU94 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(\sqrt m),\ O(m\log m)\) | Lower: $\mathrm{Q} \le \widetilde{\mathrm{Q}}$ and $\mathrm{Q} \ge \widetilde{\deg}/2 = \Omega(\sqrt m)$. Upper: $\widetilde{\mathrm{Q}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$ with $\mathrm{Q} = O(m)$. Inherits the whole $\widetilde{\deg}$-vs-$\deg$ gap of \(\widetilde{\deg}_{\varepsilon}(f)\). |
| \(\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 only known to lie between $\Omega(\sqrt m)$ (from $\widetilde{\deg}$) and $O(m)$ here. |
| \(\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)\)), which is pinned only to $[\Omega(\sqrt m), O(m)]$ here. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Omega(\sqrt m),\ O(m)\) | Squeezed between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which are equal up to constants and known here only to $[\Omega(\sqrt m), O(m)]$. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Omega(\sqrt m),\ O(m)\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, with $\lambda = \Omega(\sqrt m)$ below and $\mathrm{Q} = O(m)$ above. Note $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(m)$ anyway, so the positive adversary cannot prove more than $\Theta(m)$ here even in principle. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\Theta(m)\) putative | Upper: for $m \ge 5$ the property is a disjoint union of $m(m-1)(m-2)$ subcubes of codimension $3m-6$, and the sum of their indicator monomial products is nonzero exactly on the scorpions, so $\mathrm{ndeg} \le 3m-6$. Lower: the restriction of the \(\mathrm{Q}_{0}(f)\) entry turns $\mathrm{SCORP}_m$ into $\mathrm{AND}_{m-3}$, a polynomial nonzero exactly at $1^k$ is a multiple of $\prod_i x_i$, and restrictions never increase $\mathrm{ndeg}$, so $\mathrm{ndeg} \ge m-3$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\Theta(m)\) | $\mathrm{N}\mathrm{Q}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ exactly [deWolf03], and $\mathrm{ndeg} = \Theta(m)$ here. deWolf03 |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\Theta(m)\) | Sandwiched: $\mathrm{ndeg}(f) \le \mathrm{rdeg}(f) \le \deg(f)$, with $\mathrm{ndeg} = \Theta(m)$ and $\deg = 3m-6$ here. Rational functions buy nothing exactly, just as they buy nothing on \(\mathrm{CONN}_m\). |
| \(\deg_p(f)\) Mod-p degree | \(3m-6 \text{ for } p \ge 5\) putative | Reduce the integer multilinear polynomial mod $p$: the top coefficient of $\prod_{e \in T}x_e$ is exactly $-6$, the six orderings of one triple $\{s,t,b\}$ each contributing $-1$ (see \(\deg(f)\)), so it survives modulo every prime $p \ge 5$ and $\deg_p = \deg = 3m-6$. It does not survive mod $2$ or mod $3$, and indeed exhaustive computation gives $\deg_2 = 6,\,10,\,13$ at $m = 5,6,7$ against $3m-6 = 9,\,12,\,15$ -- small characteristic genuinely helps on the scorpion, which is why \(\deg_2(f)\) is left unrecorded rather than guessed. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(m)\)· | The same sandwich as \(\mathrm{prt}_{\varepsilon}(f)\) survives the relaxation, $\mathrm{RC}(f) \le \overline{\mathrm{prt}}(f) + O(1) \le \mathrm{prt}(f) + O(1) = O(m)$; medium confidence because the $\mathrm{RC}$ containment is the zoo's own reading of [JainKlauck10] against the LP of [KLLRX15]. JainKlauck10 KLLRX15 |
Separations it witnesses
-
Not a separation between measures, but the separation the evasiveness literature cares about: a nontrivial graph property with $\mathrm{D} = \Theta(\sqrt N)$ rather than $N$. Monotonicity is what makes the Aanderaa-Karp-Rosenberg conjecture plausible, and the scorpion is the reason it must be assumed.
-
Quadratic on a natural graph property: $\mathrm{D}^{\mathrm{na}} = N$ while $\mathrm{D} = \Theta(\sqrt N)$.
-
The quadratic $\mathrm{D}^{\mathrm{na}}$-vs-$\mathrm{D}$ gap survives randomization: $\mathrm{R}^{\mathrm{na}} = \Theta(N)$ against $\mathrm{R} = \Theta(\sqrt N)$. Deleting the sting edge of a random scorpion is a measure-preserving involution touching a uniformly random pair, so a fixed query set has to cover a constant fraction of all pairs. Adaptivity, not randomness, is what makes the scorpion cheap.
Cited as a witness by
-
\(\mathrm{osss}(\mathrm{SCORPION}_m) = \Theta(m) = \Theta(\mathrm{R}_0)\)
-
\(\mathrm{nsr}(\mathrm{SCORPION}_m) = \Theta(m) = \Theta(\mathrm{s})\)
Notes
The Aanderaa-Karp-Rosenberg conjecture asserts that every nontrivial monotone graph property is evasive ($\mathrm{D} = \binom m2$ exactly). It is known for prime-power $m$ by the topological argument of [KSS84], and $\Omega(m^2)$ in general [RivestVuillemin76]; see [Miller13] for the survey. The scorpion property is not monotone -- adding an edge at the sting destroys it -- and shows that dropping monotonicity collapses the bound all the way to $\Theta(\sqrt N)$.
Randomized AKR is much weaker: the best general bound for monotone properties is $\mathrm{R} = \Omega(m^{4/3}\log^{1/3} m)$ [ChakrabartiKhot07], against a conjectured $\Omega(m^2)$.