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

Triangle finding

The flagship open problem of quantum query complexity: $\Omega(m)$ against $O(m^{5/4})$, stuck for twenty years.

total quantum arity: the adjacency matrix of a graph on $m$ vertices: $n = \binom m2 = \Theta(m^2)$ bits

Description

Does the input graph contain a copy of $K_3$? One query reveals one entry of the adjacency matrix. Detection and finding have the same complexity up to constants here, since the problem carries no promise [CGP26, Lem. 3.4].

Values below are stated in the number of vertices $m$, as the literature does; in the zoo's convention $n = \binom m2$ input variables, so $m = \Theta(\sqrt n)$.

Formal definition

$$\mathrm{TRI}_m(x) \;=\; \bigvee_{u<v<w}\ x_{uv} \wedge x_{vw} \wedge x_{uw}.$$

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Omega(m),\ O(m^{5/4})\)· Open. Best upper bound $O(m^{5/4})$ with no log factors [CLM20], after $\tilde O(m^{5/4})$ by combinatorial arguments [LeGall14, Thm. 1.1]. The ladder: $O(m^{3/2})$ by Grover, $\tilde O(m^{13/10})$ [MSS07, Thm. 4], $O(m^{35/27})$ [Belovs12span, Thm. 8], $O(m^{9/7})$ [LMS13, Thm. 7], also $\tilde O(m^{9/7})$ by nested quantum walks [JKM13]. The only lower bound is the trivial $\Omega(m)$ from a Grover search embedded in one bipartite block [CGP26, Lem. 3.3(3)]. Still open as of August 2026. CLM20 LeGall14 LMS13 Belovs12span MSS07
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(m^2) = \Theta(n)\) [CGP26, Lem. 3.3(3)] proves $\mathrm{R} = \Theta(m^2)$ for every subgraph-containment problem whose pattern keeps an edge after pinning, by embedding classical search over the $\binom m2$ pairs. Often asserted without citation, e.g. [LeGall14, §1]. CGP26
\(\mathrm{D}(f)\) Deterministic query complexity \(\binom m2 = n\) Evasive for every $m$: containing $K_k$ is elusive for all $2 \le k \le m$ [Bollobas76]. (Kahn-Saks-Sturtevant gives evasiveness of monotone properties only for prime-power $m$; Chakrabarti-Khot-Shi handle general patterns only along an arithmetic progression.) Bollobas76 CKS02
\(\mathrm{C}^1(f)\) 1-certificate complexity \(3\) Name the three edges. This is the whole difficulty: with $N$ variables and $1$-certificates of size $K$, no positive-weight adversary can prove more than $\Omega(\sqrt{NK})$ [MSS07, §1], which for $N = m^2$, $K = 3$ is exactly the $\Omega(m)$ already on record. MSS07
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\binom m2 = n\) putative The complete bipartite graph $K_{\lceil m/2\rceil,\lfloor m/2\rfloor}$ is a maximal triangle-free graph, so any unfixed pair could be set to $1$ and create a triangle; a $0$-certificate must fix every variable.
\(\mathrm{s}(f)\) Sensitivity \(\Theta(m^2) = \Theta(n)\) putative On that same $K_{m/2,m/2}$ all $2\binom{\lfloor m/2\rfloor}{2} = \Theta(m^2)$ non-edges are sensitive, and $\mathrm{s} \le \binom m2$. Note the asymmetry: on a $1$-input with a single triangle and nothing else, $\mathrm{s} = 3$, so it is $\mathrm{s}^0$ that carries the maximum.
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s} \le \mathrm{bs} \le \mathrm{C} \le \binom m2$.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{fbs}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{RC}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\chi(f)\) Conflict complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CA}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(m^2) = \Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(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{C}(f)\) Certificate complexity \(\binom m2 = n\) $\mathrm{C} = \max(\mathrm{C}^0,\mathrm{C}^1) = \max(\binom m2, 3)$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(3\) putative Sharp, and the whole story of this problem in one line. If two edges $e \ne f$ are both sensitive at a $1$-input then deleting either kills every triangle, so every triangle contains both; four sensitive edges are impossible and three must be a single triangle. Attained by a graph with exactly one triangle. Compare $\mathrm{s}^0 = \Theta(m^2)$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(3\) putative Same argument as $\mathrm{s}^1$: every sensitive block must delete an edge of every triangle, so disjoint blocks inject into the $3$ edges of any one triangle.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\Theta(m^2) = \Theta(n)\) putative The maximum in the $\mathrm{s}$ entry is attained at the $0$-input $K_{\lceil m/2\rceil,\lfloor m/2\rfloor}$, so it is the $0$-side that carries it.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}^0 \le \mathrm{bs}^0 \le \binom m2$, with $\mathrm{s}^0 = \Theta(m^2)$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(3\) putative A $1$-certificate is a triangle and cannot be smaller; every $0$-input costs $\binom m2$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(m^2) = \Theta(n)\) Squeezed between $\mathrm{fbs} = \Theta(m^2)$ and $\mathrm{C} = \binom m2$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\binom m2 = n\) Squeezed between $\mathrm{C} = \binom m2$ and $\mathrm{D} = \binom m2$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\binom m2 = n\) Squeezed between $\mathrm{C} = \binom m2$ and $\mathrm{D} = \binom m2$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\binom m2 = n\) Every edge is relevant, so a non-adaptive deterministic algorithm reads the whole adjacency matrix -- which costs nothing extra, since the property is evasive.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(m^2)$ and $\mathrm{D}^{\mathrm{na}} = \binom m2$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(m^2) = \Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(m^2)$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m^2)$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m^2)$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(m^2) = \Theta(n)\) Pinned by $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23]: a $1$-certificate is a single triangle, so $\mathrm{C}^1 = 3$ and the product is $\binom m2 \cdot 3 = \Theta(m^2)$, matching $\mathrm{R}_0 = \Theta(m^2)$ from below. Consistent with $\mathrm{Adv}^2 = \Theta(m^2)$. The lopsided certificate sizes are what make this one of the rare cases where $\mathrm{CG}$ stays at the arity; the old note justified it by the false $\mathrm{CG} \le \mathrm{D}$. CGLMSG23
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(m)\) putative Pinned exactly, and it is the barrier in the $\mathrm{C}^1$ note made into a value. Upper: $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0\mathrm{C}^1} = \sqrt{3\binom m2} = O(m)$. Lower: restrict to $K_{\lceil m/2\rceil,\lfloor m/2\rfloor}$ with the $2\binom{\lfloor m/2\rfloor}{2} = \Theta(m^2)$ within-side pairs left free; adding any one of them closes a triangle, so the restriction is $\mathrm{OR}$ on $\Theta(m^2)$ variables, and $\mathrm{Adv}$ is monotone under restriction, giving $\mathrm{Adv} \ge \mathrm{Adv}(\mathrm{OR}_{\Theta(m^2)}) = \Omega(m)$. So the positive-weights adversary is stuck at the trivial bound for a structural reason, and any improvement on $\Omega(m)$ needs negative weights or a different method entirely.
\(\lambda(f)\) Spectral sensitivity \(\Theta(m)\) putative Squeezed: $\sqrt{\mathrm{s}(f)} \le \lambda(f) \le \mathrm{Adv}(f)$, with $\mathrm{s} = \Theta(m^2)$ and $\mathrm{Adv} = \Theta(m)$. Spectral sensitivity is therefore a tight certificate that the positive adversary cannot go past $m$ here.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(m)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = \Theta(m^2)$ here.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Omega(m),\ O(m^{5/4})\) Open, and open in exactly the same window as $\mathrm{Q}$. Upper: $\widetilde{\deg} \le 2\mathrm{Q} = O(m^{5/4})$ by the polynomial method applied to [CLM20]. Lower: $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(m)$ by Nisan-Szegedy, which is all that is known -- the Bun-Kothari-Thaler machinery that settled $\widetilde{\deg}$ for \(\mathrm{SURJ}_{N,R}\) and pushed \(\mathrm{DIST}^k_n\) has not been made to say anything here. Exact $\deg$ is left blank on purpose: the top Fourier coefficient $\sum_x(-1)^{|x|}\mathrm{TRI}_m(x)$ is nonzero for $3 \le m \le 7$ -- it is $-1, 3, -4, -3, -61$ -- but it is tiny compared with $2^{\binom m2}$ and nothing rules out its vanishing at larger $m$, so $\deg = \binom m2$ stays a conjecture. CLM20
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Omega(m),\ O(m^{5/4})\) The approximate $\gamma_2$ norm equals $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), so it inherits the open window too.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(m^2) = \Theta(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)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(m^2) = \Theta(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)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Omega(m),\ O(m^{5/4})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so the general adversary inherits the open window verbatim: computing $\mathrm{Adv}^{\pm}(\mathrm{TRI}_m)$ is the triangle problem.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Omega(m),\ O(m^{5/4})\) Squeezed between $\mathrm{Adv}^{\pm}$, which the multiplicative adversary dominates, and $\mathrm{Q}$, which it lies below -- and those two have the same open window here. So the strengthening from additive to multiplicative buys nothing on the triangle problem either: any improvement would be an improvement to $\mathrm{Q}$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(m),\ O(m^{5/4}\log m)\) Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so the window is the $\mathrm{Q}$ window plus a log. Noise is not where the difficulty lies.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(m^2)\) Between $\mathrm{R} = \Theta(m^2)$ and $O(\mathrm{R}\log \mathrm{R}) = O(m^2\log m)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Classically the problem is already maximally hard, so noise costs only a log.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(2^{-\Theta(m^2)}\) putative Exponentially small, because a uniform graph has a triangle with probability $1 - 2^{-\Theta(m^2)}$: the number of triangle-free graphs on $m$ vertices is $2^{(1/4+o(1))m^2}$ against $2^{\binom m2}$ in all. Write $q = \Pr[\mathrm{TRI}_m = 0]$. Upper: an edge is pivotal only if deleting it destroys every triangle, in particular only on graphs whose $\mathrm{TRI}$ value is $0$ after the flip, so $\mathrm{Inf}_e \le 2q$ and $\mathrm{I} \le 2\binom m2 q = 2^{-\Theta(m^2)}$. Lower: Poincare, $\mathrm{I} \ge \mathrm{Var} = \Theta(q)$. So on the uniform measure the triangle problem is invisible, which is why every lower bound for it argues against a planted distribution instead.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(2^{-\Theta(m^2)}\) For Boolean-valued $f$ the $L_1$ and $L_2$ influences coincide (\(\mathrm{I}^{1}(f)\)), so this is the $\mathrm{I}(f)$ row verbatim.
\(\mathrm{MaxInf}(f)\) Maximum influence \(2^{-\Theta(m^2)}\) Exactly $\mathrm{I}(f)/\binom m2$: $\mathrm{TRI}_m$ is edge-transitive, so every coordinate has the same influence. The $\binom m2$ is swallowed by the exponent.
\(\mathrm{Var}(f)\) Variance \(2^{-\Theta(m^2)}\) From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: a uniform graph contains a triangle with probability $1-2^{-\Theta(m^2)}$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(m^2)\) putative Upper: $\mathrm{RS}\le\mathrm{R}=\Theta(m^2)$ [BenDavidKothari18]. Lower: start from the complete bipartite graph $K_{m/2,m/2}$, which is triangle-free, and note that adding any one of the $2\binom{m/2}2=\Theta(m^2)$ missing intra-side edges creates a triangle, since two vertices on the same side always share a neighbour. Starring any one of those edges sabotages the input, so finding a $\ast$ is finding a marked coordinate among $\Theta(m^2)$. BenDavidKothari18
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(m^2)\) $\mathrm{noisyR}\le\mathrm{R}$ [BenDavidBlais20composition], and $\mathrm{R}=\Theta(m^2)=\Theta(\text{arity})$ forces $\mathrm{noisyR}=\Theta(\mathrm{R})$ [CKMPSS23]. CKMPSS23 BenDavidBlais20composition
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(m^2)\)· putative Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(m^2)$. Lower: the Erdos-Renyi measure $G(m,c/m)$ is a product distribution on the edge slots, and $c$ can be chosen so that a triangle exists with probability $1/2$. A tree of depth $\varepsilon m^2$ leaves a pair set that still spans $(1-3\varepsilon)\binom m3$ triples, each independently present with probability $c^3/m^3$, so conditioned on any transcript the posterior probability of a triangle in the unread part stays bounded away from $0$ and $1$.
\(\deg_2(f)\) Mod-2 degree \(\Theta(m^2)\) putative Set every edge at vertex $1$ to $1$ and leave the rest free: the graph then has a triangle exactly when some edge survives among the other $m-1$ vertices, so the restriction is $\mathrm{OR}_t$ with $t=\binom{m-1}2$. Over $\mathbb{F}_2$, $\mathrm{OR}_t=1+\prod_i(1+x_i)$ has degree $t$, and mod-$2$ degree never increases under restriction; the ceiling is $\binom m2$.
\(\deg_p(f)\) Mod-p degree \(\Theta(m^2)\) putative Same restriction as \(\deg_2(f)\): $\mathrm{OR}_t=1-\prod_i(1-x_i)$ has $\mathbb{F}_p$-degree $t=\binom{m-1}2$, and $\deg_p\le\deg\le\binom m2$.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(m^2)\) $\deg_2\le\mathrm{D}^{\oplus}\le\mathrm{D}$: a depth-$t$ parity tree writes $f$ as a sum of products of at most $t$ affine forms over $\mathbb{F}_2$. With $\deg_2=\Theta(m^2)$ and $\mathrm{D}=\binom m2$ the two ends meet.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(\Theta(m^2)\) $\mathrm{D}^{\oplus}\le\dim_{\mathbb{F}_2}(f)\le\binom m2$ (\(\dim_{\mathbb{F}_2}(f)\) vs \(\mathrm{D}^{\oplus}(f)\)), and $\mathrm{D}^{\oplus}=\Theta(m^2)$.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^{\Theta(m^2)}\) putative Sparsity does not increase under restriction, and the restriction of \(\deg_2(f)\) is $\mathrm{OR}_t$ with $t=\binom{m-1}2$, whose $\pm1$ form $1-2\prod_i(1-x_i)$ has all $2^t$ Fourier coefficients nonzero. The ceiling is $2^{\binom m2}$.
\(\hat{L}_1(f)\) Spectral norm \(2^{\Omega(m)}\) putative Restrict to $m/3$ vertex-disjoint triangles with all other edges set to $0$: the restriction is $\mathrm{OR}_{m/3}\circ\mathrm{AND}_3$, the blocks are disjoint so $\hat L_1$ multiplies, and $\hat L_1(\prod_i(1-\mathrm{AND}_3))=(2-2^{-2})^{m/3}$; with $\hat L_1(1-2P)\ge2\hat L_1(P)-1$ this gives $2^{\Omega(m)}$. Restriction can only decrease $\hat L_1$, and the ceiling is $2^{\mathrm{D}}=2^{\binom m2}$ (\(\hat{L}_1(f)\) vs \(\mathrm{D}(f)\)).
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(2^{-\Theta(m^2)}\) $\delta\,\mathrm{MaxInf}\le\mathrm{NS}_\delta\le\delta\,\mathrm{Inf}$, and both recorded influence values are $2^{-\Theta(m^2)}$: a uniformly random graph contains a triangle with overwhelming probability, so resampling a $\delta$-fraction of the edges almost never changes the answer.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - 2^{-\Theta(m^2)}\) $\mathrm{Stab}_\rho=1-2\,\mathrm{NS}_\delta$ at $\rho=1-2\delta$, and $\mathrm{NS}_\delta=2^{-\Theta(m^2)}$. Triangle-freeness is a vanishingly rare event, so the function is nearly constant and nearly perfectly stable.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(3\) putative Upper: $\sum_{\{a,b,c\}}x_{ab}x_{bc}x_{ca}$ is a sum of non-negative terms, positive exactly on the graphs with a triangle, so $\mathrm{ndeg}\le\mathrm{C}^1=3$. Lower: fix one triple free and every other edge to $0$; a multilinear polynomial in three variables vanishing on the other seven points must be a multiple of $x_1x_2x_3$, and nondeterministic degree does not increase under restriction. deWolf03
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(2\) $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil$ [deWolf03] and $\mathrm{ndeg}=3$. Two queries suffice for a nondeterministic quantum verifier even though $\mathrm{Q}=\Omega(m)$. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(m^2)\) putative $\mathrm{rdeg}=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}\le\mathrm{C}=\binom m2$. The complement side is the expensive one: on the restriction of \(\deg_2(f)\) the complement is $\mathrm{NOR}_t$ with $t=\binom{m-1}2$, and a polynomial nonzero exactly at $0^t$ is a multiple of $\prod_i(1-x_i)$, so $\mathrm{ndeg}(\bar f)\ge\binom{m-1}2$. deWolf03
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(m^2)\)· putative $\mathrm{UC}^0\ge\mathrm{C}^0=\binom m2$, so the question is the $1$-side. For the input consisting of a single triangle $T$, any certificate must fix a triangle to $1$ and can only fix edges of $T$, so its $1$-part is exactly $T$. For two distinct triangles $T$ and $U$ the graph $T\cup U$ then lies in both certificates unless one of them fixes an edge of the other to $0$; orienting each such pair, some triangle beats at least half the others, and since each edge lies in $m-2$ triangles its $0$-set has size $\Omega(m^2)$. Hence $\mathrm{UC}^1=\Theta(m^2)$ too, and the ceiling is $\mathrm{UC}=\binom m2$. BHT17
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(m),\ O(m^2)\) $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg}=\Omega(m)$ and $\mathrm{R}=\Theta(m^2)$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(m^{5/4})\) $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon=O(m^{5/4})$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)). The $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$ route gives no lower bound here, since no sign-degree bound is recorded for triangle finding.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(m^{5/4})\) $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15]; see \(\mathrm{rdeg}_{\varepsilon}(f)\). Post-selection is in particular at least as strong as the $O(m^{5/4})$ quantum walk. MahadevdeWolf15
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(m^2)}\) putative Every $0$-input needs all $\binom m2$ edges read, since $\mathrm{C}^0=\binom m2$, so distinct triangle-free graphs end at distinct leaves. The $2^{m^2/4}$ bipartite graphs on a fixed balanced vertex split are all triangle-free, so $\mathrm{DTsize}\ge2^{m^2/4}$; the ceiling is $2^{\binom m2}$.

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

Separations it witnesses

Notes

Two barriers are worth knowing. The certificate-complexity barrier above caps the positive-weight adversary at $\Omega(m)$. And [BalodisIraids15] show $\mathrm{Q}(\mathrm{TRI}_m) = \Omega(\sqrt m \cdot \mathrm{Q}(\mathrm{GC}_m))$ for graph collision, so any super-Grover bound for graph collision -- itself stuck at the trivial bound -- would immediately break the triangle barrier.

A restricted-model lower bound often misquoted as an unconditional one: [BelovsRosmanis14, Prop. 13] gives $\Omega(m^{9/7}/\sqrt{\log m})$ for the non-adaptive learning graph complexity of the triangle certificate structure, and unconditionally only for the edge-weighted triangle-sum problem. Le Gall's $\tilde O(m^{5/4})$ therefore separates adaptive from non-adaptive learning graphs rather than contradicting anything.