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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = \Theta(m^2)\) against \(\mathrm{Stab}_{\rho}(f) = 1 - 2^{-\Theta(m^2)}\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \tilde\Theta(m^2)\) against \(\mathrm{C}^1(f) = 3\)
-
\(\mathrm{cjdeg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\mathrm{cjdeg}_{\varepsilon}(f) = \Omega(m),\ O(m^2)\) against \(\mathrm{NQ}(f) = 2\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{s}^1(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{\Omega(m)}\) against \(\mathrm{s}^1(f) = 3\)
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{CG}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\Theta(m^2)}\) against \(\mathrm{CG}(f) = \Theta(m^2) = \Theta(n)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \tilde\Theta(m^2)\) against \(\mathrm{NQ}(f) = 2\)
-
\(\mathrm{cjdeg}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{cjdeg}_{\varepsilon}(f) = \Omega(m),\ O(m^2)\) against \(\mathrm{C}^1(f) = 3\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{bs}^1(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{\Omega(m)}\) against \(\mathrm{bs}^1(f) = 3\)
-
\(\dim_{\mathbb{F}_2}(f_n) \to \infty \ \text{ while } \ \mathrm{Stab}_{\rho}(f_n) = O(1)\)from \(\dim_{\mathbb{F}_2}(f) = \Theta(m^2)\) against \(\mathrm{Stab}_{\rho}(f) = 1 - 2^{-\Theta(m^2)}\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{\Omega(m)}\) against \(\mathrm{C}^1(f) = 3\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{NQ}(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{\Omega(m)}\) against \(\mathrm{NQ}(f) = 2\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{ndeg}(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{\Omega(m)}\) against \(\mathrm{ndeg}(f) = 3\)
Separations it witnesses
-
A candidate for a large gap that nobody can pin down: $\mathrm{R} = \Theta(m^2)$ against a $\mathrm{Q}$ known only to lie in $[\Omega(m), O(m^{5/4})]$, so the true exponent of $\mathrm{R}$ vs $\mathrm{Q}$ here is somewhere in $[8/5, 2]$.
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.