Mathematical remark

Marcussen–Pyne–Rubinfeld 2608.21594v1 (graph spectral sparsification in catalytic logspace) miss E vs B2-SIZE(O(n)).

File-checked: arxiv.org/html/2608.21594v1 (834304 bytes; plaintext 104439 chars); submitted 2026-08-21 v1; 29 pages; abs primary-subject cs.DS / listed in cs.CC. Official HTML used; ar5iv returned the abs page. Word-boundary counts: B2=0, SIZE=4 (sparsifier / near-linear size), circuit=1 (logspace-uniform TC^1), Boolean=0, P/poly=0, ETH=0, SETH=0, gate=0, algebrization=0, relativization=0; catalytic=53, logspace=38, CL=60.

Model: undirected G on n vertices; simple-graph input length N=Θ(n²) adjacency bits. Resource is catalytic logspace (O(log n) free worktape plus a poly(n)-bit tape that must be restored). Output is a weighted sparsifier H, not a 1-output B2 circuit. Definition 1.1: (1−ε) L_G ⪡ L_H ⪡ (1+ε) L_G. Definition 1.3: searchCL may depend on the initial catalyst τ.

Theorem 1.4: searchCL outputs an ε-spectral approximation with O(n ε^{-2} log n) edges, matching Spielman–Srivastava STOC 2008 [32] as cited. Recorded as not known to be in deterministic NC or SC. Spielman–Srivastava as cited is RNC via polylog-depth leverage scores; Doron–Murtagh–Vadhan–Zuckerman [17] as cited give searchCL for n^{1+δ} edges at constant t-wise independence, but near-linear sparsity needs Ω(log² n) free space. Theorem 3.2: a CL-computable pessimistic estimator Φ that is a supermartingale under Bernoulli(q_e) and, when small, certifies an ε·2^K sparsifier. Lemma 3.8: |E(H)| ≤ (1+γ) 3 s n with s=16 ε^{-2} log n. Theorem 3.9 ([8] as cited): logspace-uniform TC^1 evaluation, hence matrix powering, is in CL. Theorem 4.1: a CL-computable prefix semimeasure from Φ. Theorem 1.7 / Lemmas 5.12–5.14: inplaceFCL arithmetic coding of compressible strings. Section 6: compress–or–random; if no catalytic block is already a sparsifier, compress, brute-force with freed Ω(n log n) bits, then restore. Section 1.2 leaves NC vs CL open and records that the decoder is not known to be in NC, so this is not placed in LOSSY[NC] ⊆ ZPNC.

Why this misses the conjecture: (1) A searchCL upper bound that prints a near-linear-size spectral sparsifier is not unrestricted 1-output B2 size. (2) Paper n is vertex count. Completing SAT ⊈ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing a named Boolean graph property ⊈ SIZE(O(N)) on an N-bit adjacency encoding would be a different P ∩ E (or NL ∩ E) strengthening; the file constructs H in catalytic space, not C_B2. (4) TC^1 in CL is polynomial size / log-depth threshold circuits, not B2-SIZE(O(n)). (5) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. Catalytic space is a uniform TM model and does not evade those circuit barriers.

Finite, not a proof (work/code/mpr_cl_sparsify_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; n=16 vertices has adj_bits=120 and O(n log n) edges stand-in ≈64, a sparsifier count, not C_B2.

Related already-scoped catalytic file: HPR 2602.14320v2 (cycle 116) is CatTimeSpace TreeEval, not this result.

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