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

Graph connectivity

The monotone graph property everyone checks first: evasive, $\mathrm{R} = \Theta(N)$, and $\mathrm{Q} = \Theta(N^{3/4})$.

total basic arity: $N = \binom{m}{2}$ bits, the adjacency matrix of an $m$-vertex graph

Description

Given the adjacency matrix of an undirected graph on $m$ labelled vertices, decide whether the graph is connected. Monotone (adding edges never disconnects) and nontrivial.

Formal definition

$$\mathrm{CONN}_m(G) = 1 \iff G \text{ has one connected component}.$$

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(\binom{m}{2} = N\) Evasive for every $m \ge 2$: an adversary can always force all $\binom m2$ queries. One of the earliest properties proved evasive, and the model case for the Aanderaa-Karp-Rosenberg conjecture. Bollobas76 KSS84
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(m^2) = \Theta(N)\) Upper: $\mathrm{R} \le \mathrm{D}$. Lower: $\Omega(m^2)$ -- take a random graph on the threshold and note that a spanning-tree/isolated-vertex distinction survives $o(m^2)$ random probes. So connectivity is one of the (few) monotone graph properties where randomized AKR is known.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(m^2) = \Theta(N)\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- connectivity is randomised-evasive up to a constant. CKMPSS23
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) [DHHM06]: Grover-search the neighbourhoods in a BFS, $O(m^{3/2})$ queries; and $\Omega(m^{3/2})$ by the quantum adversary. Strong connectivity of a digraph, minimum spanning tree and single-source shortest paths in the adjacency-matrix model are all $\Theta(m^{3/2})$ too. DHHM06
\(\mathrm{C}^1(f)\) 1-certificate complexity \(m-1\) A spanning tree certifies connectivity.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(m^2)\) To certify disconnectedness you must exhibit a cut $(S,\bar S)$ with all $|S|(m-|S|)$ edges absent; the adversary makes $|S| = m/2$, so $\mathrm{C}^0 = \Theta(m^2)$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(N^{3/4})$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(N^{3/4})$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(m^2) = \Theta(N)\) $\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^2) = \Theta(N)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(m^{3/2}) = \Theta(N^{3/4})$ here.
\(\mathrm{s}^1(f)\) 1-sensitivity \(m-1\) putative At a connected $G$ the sensitive coordinates are exactly the bridges -- adding an edge can never disconnect. A tree has $m-1$ bridges and nothing has more.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\lfloor m^2/4 \rfloor\) putative At a disconnected $G$ the sensitive coordinates are exactly the absent pairs whose insertion connects the whole graph, so $G$ must have precisely two components and every crossing pair is sensitive. Balancing them gives $\lfloor m/2\rfloor\lceil m/2\rceil$. Deleting an edge from a disconnected graph never connects it, so nothing else contributes.
\(\mathrm{s}(f)\) Sensitivity \(\lfloor m^2/4 \rfloor = \Theta(N)\) putative The $0$-side wins by a full quadratic factor: two balanced cliques are as $0$-sensitive as a graph can be, while $1$-sensitivity is capped by the $m-1$ bridges of a tree.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(m-1\) putative Squeezed between $\mathrm{s}^1 = m-1$ and $\mathrm{C}^1 = m-1$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(m^2) = \Theta(N)\) Squeezed between $\mathrm{s}^0 = \lfloor m^2/4\rfloor$ and $\mathrm{C}^0 = \Theta(m^2)$.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(m^2) = \Theta(N)\) From $\mathrm{bs}^0$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(m^2) = \Theta(N)\) Squeezed between $\mathrm{bs}$ and $\mathrm{C}$, both $\Theta(N)$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(m^2) = \Theta(N)\) $\mathrm{FC} = \mathrm{fbs}$ exactly, by LP duality, and $\mathrm{fbs} = \Theta(m^2)$ here.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(m^2) = \Theta(N)\) $\mathrm{RC} = \Theta(\mathrm{fbs})$, and $\mathrm{fbs} = \Theta(m^2)$ here.
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(m^2) = \Theta(N)\) $\max(\mathrm{C}^0, \mathrm{C}^1)$, i.e. the cut side.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(m-1\) putative Both kinds of certificate need $m-1$ coordinates and both achieve it: a spanning tree on the connected side, an isolated vertex on the disconnected side. So $\mathrm{C}_{\min} = \Theta(\sqrt{\mathrm{C}})$ -- connectivity is one of the cleanest natural examples of certificate complexity that varies quadratically across inputs.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\binom{m}{2} = N\) Every pair is relevant, so a non-adaptive algorithm reads everything. Here that is no loss at all: $\mathrm{D}=N$ already, connectivity being evasive.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}} = N$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D} = N$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D} = N$.
\(\deg(f)\) Exact degree \(\binom{m}{2} = N\) putative Full degree, so connectivity is evasive for the polynomial method too. The coefficient of the top monomial $\prod_e x_e$ in the multilinear extension is $\sum_{S}(-1)^{N-|S|}\mathrm{CONN}(S) = \pm\sum_{S \text{ connected}}(-1)^{|S|}$, and the classical alternating count of connected spanning subgraphs of $K_m$ is $(-1)^{m-1}(m-1)!$ -- never zero. Verified by exact expansion for $m \le 6$, where the top coefficient is $\pm 2, \pm 6, \pm 24, \pm 120$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\deg/2 = N/2$ and $\mathrm{D} = N$. Exact quantum computation buys at most a factor $2$ on connectivity, while bounded error buys the $\Theta(N^{3/4})$ of \(\mathrm{Q}_{\varepsilon}(f)\).
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(m^{3/2}),\ O(m^2)\) Between $\mathrm{Q} = \Theta(m^{3/2})$ and $\mathrm{Q}_{\mathrm{E}} = O(m^2)$. Whether zero-error connectivity is as hard as exact connectivity is open as far as the zoo knows; note that the [DHHM06] algorithm is Grover-based and therefore genuinely bounded-error.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\binom{m}{2} = N\) putative A monochromatic subcube partition writes $f$ as a sum of indicators of conjunctions of $\le \mathrm{SP}$ literals with no cancellation, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg = \mathrm{D} = N$ and the whole chain collapses.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\binom{m}{2} = N\) putative Pinned by the same collapse; see \(\mathrm{SP}(f)\). Note the contrast with $\mathrm{C}_{\min} = m-1$: a spanning tree is a perfectly good certificate, but no unambiguous family can be narrow anywhere near everywhere.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(m^2) = \Theta(N)\) Squeezed between $\mathrm{fbs} = \Theta(m^2)$ and $\mathrm{C} = \Theta(m^2)$.
\(\deg_2(f)\) Mod-2 degree \(\lfloor m^2/4 \rfloor\) putative Over $\mathbb{F}_2$ the coefficient of $x_S$ is the number of connected spanning subgraphs of $(V,S)$ mod $2$, and that count is odd exactly when $(V,S)$ is connected and bipartite. (Proof: both sides satisfy the deletion-contraction recursion $N(H) = N(H/e)+N(H-e)$ mod $2$ -- contracting a non-bridge of a bipartite graph creates an odd cycle, contracting a bridge preserves bipartiteness -- with the same base cases.) So $\deg_2$ is the largest number of edges in a connected bipartite graph on $m$ vertices, namely $K_{\lfloor m/2\rfloor,\lceil m/2\rceil}$. Verified exhaustively over all graphs on $m \le 6$ vertices, and the value $2,4,6,9,12$ for $m = 3,\dots,7$. So $\deg_2 = (\tfrac12+o(1))\deg$ -- connectivity loses exactly half its degree over $\mathbb{F}_2$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(m^2 2^{-m})\) putative A uniformly random graph is connected with probability $1-\Theta(m2^{-m})$, and a pair $uv$ is sensitive only in the two degenerate ways: $uv$ is a bridge with one endpoint pendant, or one endpoint is isolated and $uv$ would attach it. Each has probability $2^{2-m}$, so $\mathrm{I}(f) = (1+o(1))\binom m2 2^{3-m}$. Confirmed numerically: the ratio to $\binom m2 2^{3-m}$ is $0.50,\,0.63,\,0.78,\,0.91,\,0.97$ at $m = 3,\dots,7$. Average sensitivity is thus exponentially below $\mathrm{s} = \lfloor m^2/4\rfloor$ -- connectivity is a wildly unbalanced function.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Omega(m),\ O(m^{3/2})\) Lower: $\mathrm{bs} \le 6\widetilde{\deg}^2$ [NS94] against $\mathrm{bs} = \Theta(m^2)$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(m^{3/2})$. The $\Omega(m^{3/2})$ lower bound for \(\mathrm{Q}_{\varepsilon}(f)\) is an adversary bound, not a polynomial one, so the zoo does not know that $\widetilde{\deg}$ matches it.
\(\lambda(f)\) Spectral sensitivity \(\Omega(m),\ O(m^{3/2})\) Lower: $\lambda \ge \sqrt{\deg} = \sqrt{N} = \Theta(m)$ [Huang19]. Upper: $\lambda \le \sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{\lfloor m^2/4\rfloor(m-1)} = \Theta(m^{3/2})$, far below $\mathrm{s} = \Theta(m^2)$. Exact diagonalisation of the sensitivity graph gives $\lambda = 2,\ 3.126,\ 4.356,\ 5.674$ at $m = 3,4,5,6$, i.e. $\lambda/m^{3/2} = 0.385,\ 0.391,\ 0.390,\ 0.386$ -- so the upper end looks like the truth, and $\lambda$ would then match $\mathrm{Q} = \Theta(m^{3/2})$ exactly.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(m^2) = \Theta(N)\) 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^2)$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(m^2) = \Theta(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)\)); here $\mathrm{R} = \Theta(m^2)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(m^2) = \Theta(N)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(m^2)$. Yao77
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(m^2)$ meets $\mathrm{R} = \Theta(m^2)$. Connectivity therefore composes perfectly: $\mathrm{R}(\mathrm{CONN}_m \circ g^N) = \Omega(N\,\mathrm{R}(g))$.
\(\chi(f)\) Conflict complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) \lesssim \mathrm{RS}(f)$, both $\Theta(m^2)$ here. The whole inner-measure chain $\chi \lesssim \mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$ collapses on a randomised-evasive function.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(m^2) = \Theta(N)\) Squeezed inside $\mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$, with $\mathrm{RS} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(m^2) = \Theta(N)\) Squeezed between $\bar\chi = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(m^2) = \Theta(N)\) Squeezed between $\mathrm{LR} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(m^2) = \Theta(N)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ [ABIKPS17], and $\mathrm{fbs} = \Theta(m^2)$ here. ABIKPS17
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(m^2) = \Theta(N)\) $\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^2)$ here. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(m^2) = \Theta(N)\) Entanglement buys nothing beyond the non-signaling value: $\mathrm{CG}^{*} = \Theta(\mathrm{CA}) = \Theta(m^2)$. Note the contrast with \(\mathrm{Q}_{\varepsilon}(f)\), where quantum queries do buy the factor $\sqrt m$. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(m^2) = \Theta(N)\) The non-signaling relaxation is already $\Theta(\mathrm{CA}) = \Theta(m^2)$. CGLMSG23
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(m^3) = \Theta(N^{3/2})\) putative Both ends of the [CGLMSG23] sandwich land on $m^3$: $\mathrm{Adv}(f)^2 = \Theta(m^{3/2})^2 = \Theta(m^3)$ from below, and $\mathrm{C}^0\mathrm{C}^1 = \Theta(m^2)\cdot(m-1) = \Theta(m^3)$ from above. So connectivity is one of the sharpest examples in the zoo of $\mathrm{CG}$ exceeding the arity -- $\mathrm{CG} = \Theta(N^{3/2})$ on $N = \binom{m}{2}$ variables. CGLMSG23
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{prt}(f) + O(1) \le 2\,\mathrm{R}(f) + O(1)$, with $\mathrm{RC} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$ here. The LP bound is tight on connectivity, so the $\Theta(N)$ randomized lower bound is already visible to the partition bound. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(m^2) = \Theta(N)\)· The \(\mathrm{prt}_{\varepsilon}(f)\) sandwich survives the relaxation, $\mathrm{RC}(f) \le \overline{\mathrm{prt}}(f) + O(1) \le \mathrm{prt}(f) + O(1) = O(m^2)$; medium confidence because the $\mathrm{RC}$ containment is the zoo's own reading of [JainKlauck10] against the LP of [KLLRX15]. JainKlauck10 KLLRX15
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(m) = \Theta(\sqrt N)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m^2)$ here. The $1$-side already has a classical certificate of size $m-1$ (a spanning tree); what the quantum verifier compresses is the $\Theta(m^2)$-edge cut on the $0$-side. Aaronson08
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(m^2),\ O(m^2\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^2)$. Whether the logarithm is needed is exactly the question of whether noisy connectivity is harder than noiseless; the $\mathrm{I}\log\mathrm{I}$ lower bound gives nothing, $\mathrm{I}(f)$ being exponentially small. FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(m^{3/2}),\ O(m^{3/2}\log m)\) Generic: $\mathrm{Q}(f) \le \widetilde{\mathrm{Q}}(f) = O(\mathrm{Q}(f)\log \mathrm{Q}(f))$, with $\mathrm{Q} = \Theta(m^{3/2})$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) The recorded $\Omega(m^{3/2})$ lower bound for \(\mathrm{Q}_{\varepsilon}(f)\) is an adversary bound [DHHM06], so $\mathrm{Adv} = \Omega(m^{3/2})$; and $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = O(m^{3/2})$. The positive adversary is exactly optimal here, and it meets its own certificate barrier $\mathrm{Adv} \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(m^{3/2})$ -- connectivity is one of the cleanest total functions where that barrier is attained rather than obstructive. DHHM06
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(m-1\) putative Exactly. Upper: the spanning-tree generating polynomial $\tau(G) = \sum_{T}\prod_{e \in T}x_e$ (the reduced Laplacian determinant of the matrix-tree theorem) is multilinear of degree $m-1$ and is nonzero precisely when $G$ is connected, all its terms being non-negative. Lower: fix a spanning tree's $m-1$ pairs free and all other pairs absent; the restriction is $\mathrm{AND}_{m-1}$, a polynomial nonzero exactly at $1^{k}$ is a multiple of $\prod_i x_i$, and restrictions never increase $\mathrm{ndeg}$. So the nondeterministic degree of connectivity is $\Theta(\sqrt N)$, a quadratic drop from $\deg = N$.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\lceil (m-1)/2 \rceil = \Theta(\sqrt N)\) $\mathrm{N}\mathrm{Q}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ exactly [deWolf03], and $\mathrm{ndeg} = m-1$ here. Nondeterministic quantum connectivity thus costs $\Theta(\sqrt N)$, below even $\mathrm{Q} = \Theta(N^{3/4})$: guessing a spanning tree is much easier than finding one. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(m^2) = \Theta(N)\) putative Rational functions buy essentially nothing. Use the characterisation $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \mathrm{C}(f)$: the $0$-side is expensive, since fixing all pairs inside a balanced bipartition $(A,B)$ to present and leaving the $\lfloor m^2/4\rfloor$ crossing pairs free makes the restriction $\mathrm{OR}$, whence $\mathrm{ndeg}(\bar f) \ge \mathrm{ndeg}(\mathrm{NOR}_{\lfloor m^2/4\rfloor}) = \lfloor m^2/4\rfloor$; and $\mathrm{C} = \Theta(m^2)$ caps it. Contrast $\mathrm{ndeg} = m-1$: the asymmetry between spanning trees and cuts is exactly what rational degree cannot exploit.
\(\deg_p(f)\) Mod-p degree \(N \text{ for } p \ge m\) putative The top coefficient of the multilinear expansion is $\pm(m-1)!$ (see \(\deg(f)\)), invertible modulo every prime $p \ge m$, so $\deg_p = \deg = N$ there. For small primes it does vanish, and dramatically so: \(\deg_2(f)\) is only $\lfloor m^2/4\rfloor$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\deg_2(f) \le \mathrm{D}^{\oplus}(f) \le \mathrm{D}(f)$, with $\deg_2 = \lfloor m^2/4\rfloor$ and $\mathrm{D} = N$ here. Parity queries save at most the factor $2$ that $\mathbb{F}_2$-degree already saves -- connectivity is evasive up to a constant even for parity decision trees.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(\binom{m}{2} = N\) putative Full, so the Fourier support spans everything and no change of basis helps. The support lies in a proper subspace exactly when $f(x \oplus a) = f(x)$ identically for some $a \ne 0$, the shifted function having coefficients $(-1)^{a\cdot S}\hat f(S)$. Given $a \ne 0$, pick a vertex $u$ meeting some pair of $a$ and let $x$ be the graph consisting of the pairs of $a$ at $u$ together with all pairs inside $V \setminus \{u\}$: then $x$ is connected, while $x \oplus a$ deletes every edge at $u$ and adds none, isolating $u$. So no such $a$ exists.
\(\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) = (1+o(1))\binom m2 2^{3-m}$; see \(\mathrm{I}(f)\).
\(\mathrm{MaxInf}(f)\) Maximum influence \((1+o(1))\,2^{3-m}\) putative Connectivity is invariant under relabelling vertices and the symmetric group is transitive on pairs, so every coordinate carries the same influence and $\mathrm{MaxInf} = \mathrm{I}(f)/N = (1+o(1))2^{3-m}$. Exact computation gives $\mathrm{I}(f)/N = 0.0608$ at $m = 7$ against $2^{3-m} = 0.0625$.
\(\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)$ with $1-p = (1+o(1))m2^{1-m}$ the probability of an isolated vertex.
\(\mathrm{osss}(f)\) OSSS number \((1+o(1))\,m = \Theta(\sqrt N)\) putative Exactly $m2^{3-m}$ over $\mathrm{MaxInf} = 2^{3-m}$, both to leading order. Quadratically short of $\mathrm{D} = N = \binom m2$ and of $\mathrm{s} = \Theta(N)$: the variance is carried by the isolated-vertex event, which touches only $m-1$ coordinates.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(m) = \Theta(\sqrt N)\) putative An isolated vertex stays isolated unless one of its $m-1$ non-edges flips, so $\delta^{*} = \Theta(1/m)$. Quadratically short of $4\mathrm{s} = \Theta(N)$, so CONN is where the $\mathrm{nsr} = O(\mathrm{s})$ bound is loosest.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \((1+o(1))\,m\,2^{2-m}\big(1-(1-\delta)^{m-1}\big)\) putative Noise sensitivity is $2\Pr[f(x)=1,f(y)=0] = 2(\Pr[\text{disconnected}] - \Pr[\text{both disconnected}])$. Disconnection is dominated by a single isolated vertex, of probability $m2^{1-m}$, and a vertex is isolated in both $x$ and its $\delta$-noisy copy with probability $((1-\delta)/2)^{m-1}$ per vertex, whence the formula. Consistency: as $\delta \to 0$ it tends to $m(m-1)2^{2-m}\delta = \delta\,\mathrm{I}(f)$, exactly the recorded \(\mathrm{I}(f)\). Exact computation gives ratios $0.60,\,0.74,\,0.86,\,0.93$ to the formula at $m = 4,5,6,7$ with $\delta = 0.05$ -- the same slow $1+o(1)$ convergence as \(\mathrm{I}(f)\) itself.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - (1+o(1))\,m\,2^{3-m}\big(1-(\tfrac{1+\rho}{2})^{m-1}\big)\) putative From $\mathrm{Stab}_{\rho} = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. For every fixed $\rho < 1$ stability is $1 - \Theta(m2^{-m})$: almost all the Fourier mass of the $\pm1$ version sits on the empty set, which is why $\mathrm{I}(f) = o(1)$ while $\mathrm{s} = \Theta(N)$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(m^2) = \Theta(N)\) putative Product distributions are worst-case here. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m^2)$. Lower: split the vertices into halves $A$ and $B$ and fix every edge inside $A$ and inside $B$ to be present. The graph is then connected iff at least one of the $\lfloor m^2/4\rfloor$ free $A$-$B$ edges is present, i.e. the restriction is $\mathrm{OR}_{\lfloor m^2/4\rfloor}$, and $\mathrm{D}^{\mathrm{prod}}(\mathrm{OR}_k) = \Theta(k)$: take each bit $1$ independently with probability $1/k$, so that after $d$ observed zeros the conditional probability of $\mathrm{OR} = 1$ is $1-(1-1/k)^{k-d}$, still above $1/3$ until $d \ge 0.59k$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(m^2) = \Theta(N)\) putative The one-sided relaxation buys nothing, but for a softer reason than on \(\mathrm{MP}_m\): the $0$-side is genuinely cheap to cover unambiguously and it is still $\Theta(N)$. Cover: for each connected vertex set $S \ni v_1$ with $S \ne V$, take the certificate that specifies every edge inside $S$ together with all $|S|(m-|S|)$ cross edges absent. Each disconnected graph matches exactly one of these -- $S$ is forced to be the component of $v_1$ -- so $\mathrm{UC}^0 \le N$, and $\mathrm{UC}^0 \ge \mathrm{C}^0 = \Theta(m^2)$. The lower bound on the min is $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min} - 1$ (\(\mathrm{fbs}(f)\) vs \(\mathrm{UC}_{\min}(f)\)) with $\mathrm{fbs} = \Theta(m^2)$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(m),\ O(m^2)\) 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(m), O(m^{3/2})]$ and $\mathrm{R} = \Theta(m^2)$. Even pinning $\widetilde{\deg}$ would leave a $\sqrt N$ window here.

Separations it witnesses

Notes

Connectivity is the standard illustration of the gap between the three graph query models. In the adjacency matrix model above it is $\Theta(m^{3/2})$ quantumly; in the adjacency list model [DHHM06] give $\Theta(m)$ for a graph with $m$ edges. The zoo records the matrix model, since that is the one that is a Boolean function on $\binom m2$ bits.