Mathematical remark

Sheffield–Vassilevska Williams–Xi 2608.19092v1 (black-box reductions for all-pairs triangle detection) miss E vs B2-SIZE(O(n)).

File-checked: arxiv.org/html/2608.19092v1 (853066 bytes; plaintext 145435 chars); submitted 2026-08-19 v1; 32 pages; abs primary-subject cs.DS / listed in cs.CC. Official HTML used; ar5iv returned the abs page. Authors: Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi. Word-boundary counts: B2=0, ETH=0, SETH=0, P/poly=0, gate=0, algebrization=0; SIZE=26 (instance/query sizes); circuit=4 (arithmetic MM vs Tr(A^3)); Boolean=19 (BMM); relativization=1 (analogy); triangle=139; black-box=58; fine-grained=34; APSP=12.

Model: paper n is vertex count of an edge-weighted tripartite graph. Input length N is Θ(n²) adjacency bits (or Θ(n² log W) with weights). Resource is TM TIME and black-box oracle cost, not 1-output B2 gates. For a relation R ⊆ ℤ³, R-Triangle asks whether some triangle has weights in R; All-Edge R-Triangle asks the same for every edge. Definition 1: a (T_B, T_A)-black-box reduction is a single algorithm M, independent of R, that solves A using B-oracle calls whose T_B-costs sum to T_A. Unweighted triangle detection / BMM sit in P ⊂ E via algebraic matrix multiplication.

Theorem 1: All-edge triangle detection does not (n^{3−ε}, n^{3−δ})-black-box reduce to triangle detection (or even counting) for any ε>0 and δ>ε/3. So Vassilevska W.–Williams 2010 [45] as cited is optimal among black-box reductions. Theorem 2: All-edge R-triangle counting does not (n², n^{3−ε})-black-box reduce to R-triangle counting. The file analogizes this to a relativization-style barrier for combinatorial reductions (Question 2). Theorems 3–4 (Duraj–Kleiner–Polak–Vassilevska Williams [29] as cited): listing ↔ all-edge is tight in m and one-way tight in n. Theorem 5 (assuming ω=2): listing n² triangles black-box reduces to all-edge detection with a weaker n-exponent. Theorem 6: no non-duplicitous (n^c, n^{9/(6−c)−ε}) black-box reduction listing n² triangles → all-edge. Theorem 7: all-IJ detection (n^c, n^{(9−2c)/(4−c)})-black-box reduces to all-JK; an n^c dominance-product algorithm yields that exponent for Boolean-(min,+). File records both currently O(n^{2.69}); O(n^{2.53}) dominance would improve Boolean-(min,+). Theorems 8–13 are hypergraph-query exact-recovery bounds (all-s containment / codegree oracles on unknown r-uniform r-partite hypergraphs). The arithmetic-circuit sentence records Tr(A³) ≡ MM in the algebraic model [39, 40] as cited, non-black-box.

Why this misses the conjecture: (1) Fine-grained TIME / hypergraph query cost is not unrestricted 1-output B2 size. (2) Completing SAT ⊈ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing TRIANGLE-DEC / BMM / APSP-DEC ⊈ SIZE(O(N)) are matching P ∩ E strengthenings; completing NT ⊈ SIZE(O(N)) is the same class of strengthening. The file does not name C_B2. (4) Algebraic MM vs Tr(A³) is not Boolean B2 size. One bit of n×n MM is IP (B2-size 2n−1). PARITY has B2-size n−1. (5) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. The paper’s black-box barrier is an information-theoretic restriction on reductions that work for every R; it does not evade those circuit barriers.

Finite, not a proof (work/code/svwx_triangle_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; paper v=16 has N_und=120, 3N=360, n³=4096, n^ω≈716 (ω=2.371177 from already-scoped Alman–Williams–Balog); v=256 has N_und=32640, 3N=97920, n³=1.68e7, n^ω≈5.13e5. Thm 1 exponents (ε=0.1): detection n^{2.90} vs all-edge n^{2.967}. Those are TIME exponents / vertex counts, not C_B2.

Related already-scoped files: Williams 1312.6680v2; Bonnet et al. 2608.25212v1; Alman–Williams–Balog 2608.16884v1; Belova et al. 2307.11444v1 / 2205.07709v5. Williams–Williams FOCS 2010 body not retrieved.

No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).