REVIEW 4 major objections 5 minor 17 references
Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read First higher-degree SoS lower bounds on random regular graphs
desk verdict Genuinely new norm bounds for random regular graphs with a nice floating-component insight, but the advertised SoS switching theorem is not proven: the PSDness analysis in Appendix A is explicitly deferred. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Graph matrices with entries given by products of $p$-biased Fourier characters on edges, analyzed through the block-value method. The central identity is the block-value bound $B_q(\tau) = \max_{S:\text{ separator}} (\sqrt n\,q)^{|V(\tau)\setminus S|} \big((1-p)/p\big)^{|E(S)|/2}\,\sqrt n^{|I(\tau)|}\,\mathrm{float}(\tau\setminus S)\,(c_{\mathrm{norm}})^{|E(\tau)|}$, where $\mathrm{float}$ contributes $\sqrt n$ for each tree-like floating component. The proof machinery assigns vertex costs and edge values step-by-step via step-labelings; the distinctive ingredient is the edge-value bound in the regular setting, which replaces the i.i.d. factorization by an estimate with a $1/\sqrt n$ decay per singleton edge.
What would settle it
A concrete calculation: produce one intersection pattern, as in Proposition A.5, whose linearized shape has more tree-like floating components than the vanishing 'phantom' edges available to pay for them, causing inequality (2) of Appendix A to fail; that would invalidate the PSDness verification and hence Theorem 3.4.
Extended reading notes
Core claim
The central discovery is a pair of spectral norm bounds (Theorems 2.9 and 2.10) for graph matrices on $G_d(n)$ that match the known Erdős–Rényi bounds except for tree-like floating components: each such component disconnected from the relevant separator contributes an extra $\sqrt n$ factor to the block-value bound. These bounds are proved by combining a block-value factor-assignment scheme with an edge-value estimate for walks in random regular graphs (restated from Sarid), which pays a $\sqrt{1/n}$ decay per singleton edge instead of the vanishing expectation of the i.i.d. case. The paper then argues, via the pseudo-calibration construction of [JPR+22], that this suffices to produce a valid pseudo-expectation of degree $d_{\mathrm{sos}}<d^{1/10}$ for independent set on $G_d(n)$, with the same objective value as in $G(n,d/n)$, thereby claiming the first higher-degree Sum-of-Squares lower bound for the independent set problem on uniformly random regular graphs.
Load-bearing premise
The proof of the Sum-of-Squares theorem depends on a part that is only sketched and explicitly deferred: that the new norm bounds fit into the previous PSD analysis, with the extra $\sqrt n$ cost of each tree-like floating component always offset by enough slack.
Editorial extensions
If this is right
- If Theorem 3.4 holds, higher-degree Sum-of-Squares can certify independent sets on random $d$-regular graphs at the same $O(n/\sqrt d)$ scale as on Erdős–Rényi graphs, up to polylog factors.
- The norm-bound transfer implies that spectral analyses of average-case algorithms that rely only on graph-matrix norm bounds should port between the two distributions, provided floating tree-like components do not dominate.
- The characterization pinpoints the only structural difference: tree-like floating components in a shape carry an extra $\sqrt n$ in the norm, which future switching arguments must either avoid or pay for.
- It answers, for the independent set problem, the open question of whether higher-degree SoS lower bounds hold on random regular graphs, extending beyond the known degree-4 results.
Reading between the lines
- A reader should not infer that any i.i.d. spectral statement transfers: the paper identifies explicit shapes (floating tree-like components) where the regular-graph norm bound is strictly larger by $\sqrt n$, so the transfer is selective.
- The deferred PSDness verification is the point most likely to need new work; completing it probably requires a careful bookkeeping of 'phantom' edges in intersection terms against floating components.
- The same switching strategy is likely to apply to other SoS lower bounds built on graph-matrix machinery, but only if their PSD analyses avoid floating components or have slack to absorb the $\sqrt n$ blow-up.
- For low-degree polynomial analysis, the norm-bound result suggests a route to an explicit orthogonal-basis-free transfer, but the distinguishing power of low-degree polynomials between the two distributions sets a limit.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops spectral norm bounds for graph matrices evaluated on uniform random d-regular graphs, with the aim of transferring Erdős-Rényi norm bounds to the regular-graph setting. For shapes without floating components, the same bounds as the i.i.d. case are claimed; for each tree-like floating component, a √n blow-up is claimed. The paper then applies these bounds to switch the independent-set Sum-of-Squares lower bound of [JPR+22] to random regular graphs, asserting the first higher-degree SoS lower bound on G_d(n) (Theorem 3.4). The proof of the application is delegated to Appendix A, whose PSDness verification is explicitly deferred.
Significance. If the norm-bound theorems are correct, they provide a genuinely useful transfer mechanism between Erdős-Rényi and random regular inputs for spectral analyses, with a crisp combinatorial criterion—tree-like floating components—for when the two settings differ. The norm bounds are stated explicitly with no free parameters, and the √n blow-up per tree-like floating component is a falsifiable structural prediction. The SoS application would answer a real open question. However, the paper's headline Theorem 3.4 is not established by the submitted text, because its proof depends on a PSDness analysis that the appendix does not carry out.
major comments (4)
- [Appendix A, Lemma A.1] The four PSDness conditions (non-trivial middle shapes, intersection terms, truncation error, well-conditionedness) are the sole bridge from the norm bounds to Theorem 3.4, yet the appendix explicitly states 'we leave the full verification to later versions of this paper' after a sketch. Since Theorem 3.4 is the paper's main advertised application, this is a load-bearing gap, not a presentation issue, and the SoS lower bound cannot be considered proved in the submitted manuscript.
- [Appendix A, Proposition A.5] The key inequality |E_ψ| + phantom(ψ) ≥ |V(τP)\V(S)| + |E_ψ(S)| + |I_ψ| + |float_ψ| is asserted without proof, and the claim that 'the second multiplicity remains unassigned' and can pay for the floating-component √n blow-up is the crux of the intersection-term analysis. The text does not show how phantom-edge multiplicities are assigned in the recursive traversal, nor how the slack-function calculation absorbs the c^{|E(τ)|} factors from the new norm bound. This lemma must be proved in full before Theorem 3.4 can be claimed.
- [Lemma 2.27 and its use in Theorem 2.10] The charging argument for singleton steps is only sketched. The proof splits into the case where S(L) is a separator and the case where it is not, but the accounting for flipped vertices and excess singleton edges contains informal assertions (for example, '...or it is a flipped vertex but the extra √n factor has been offset by the first singleton step that explores it') that do not constitute a rigorous bound. The BFS items 1–8 for the non-separator case rely on an unstated minimality/matching argument. Since Lemma 2.27 is the mechanism that recovers the separator bound in the presence of singleton steps, the norm-bound theorems depend on completing this proof.
- [Theorem 2.9, Proposition 2.29, and Theorem 3.4] The range of d in Theorem 3.4 is incompatible with the concentration statement in Proposition 2.29. Theorem 2.9 requires q < d^{1/10}, while Proposition 2.29 gives failure probability c^{-q/log n}, which tends to 1 unless q/log n → ∞. For d = (log n)^2, the largest admissible q is (log n)^{1/5}, which is o(log n), so no high-probability norm bound follows in the regime d ∈ [(log n)^2, n^{0.5}] claimed in Theorem 3.4. Either the norm-bound theorems need a separate concentration argument for q ≪ log n, or the SoS theorem must restrict d to polylog^C n for a sufficiently large C.
minor comments (5)
- [Section 2.2, Theorems 2.9 and 2.10] The statement of B_q(τ) uses V(α) in a few places where it should use V(τ), and the constants c and δ are introduced somewhat vaguely; please make the dependency of c on ε and τ explicit.
- [Definition 2.7] The definition of floating component says 'no path from C to Uτ ∪ Vα'; this should be Vτ.
- [Example 3.6] The displayed polynomial p(G) = Σ_{i,j,k} χ({i,j})χ({k,j}) contains two edge factors and is therefore a degree-2 polynomial, not 'degree-1' as the text claims. The notation p also conflicts with the probability parameter p = d/n.
- [Remark 3.7] The lower bound on the degree-1 distinguisher is explicitly stated to be heuristic; if it is used to motivate the floating-component criterion, the paper should either prove it or label it as a conjecture.
- [Lemma 2.18 and Proposition 2.19] The relationship between the unscaled character G(e)-d/n and the p-biased Fourier character used in Definition 2.1 should be written out explicitly, and the q-regime 'log n ≪ q ≪ d^{1/10}' should be matched with the q lower bound in Theorem 2.9.
Circularity Check
No circular reduction found; the main theorem's PSDness verification is explicitly deferred, which is an omitted-proof gap rather than circularity.
full rationale
The paper's Section 2 norm bounds are derived from Sarid's independent edge-value bound for random regular graphs (Lemma 2.18, restated from [Sar23]) combined with the block-value machinery of prior published works [JPR+22, KPX24]. The extra sqrt(n) factor for tree-like floating components is derived in Lemma 2.28 by an explicit charging argument, not inserted as the desired bound by construction. In the SoS application, the paper reuses the pseudo-calibration moment matrix from [JPR+22] and verifies the tractability of the constraints; the remaining PSDness analysis is delegated to Appendix A, which says 'we leave the full verification to later versions of this paper.' That is a real rigor gap for Theorem 3.4, but it is not circularity: the conclusion is not assumed as an input, and no fitted parameter is renamed as a prediction. The self-citations to [JPR+22] and [KPX24] are prior published results used as tools, not as unverified self-supporting uniqueness claims. No step of the derivation reduces by definition to its own target, so the circularity score is 0; the deferred PSDness verification should instead be weighed as a completeness/correctness limitation.
Assumptions & free parameters
assumptions (5)
- domain assumption Edge-value bound from Sarid 2023 (Lemma 2.18, Corollary 3.6 of [Sar23])
- domain assumption Block-value bound machinery from [JPR+22, KPX24, HKPX23]
- domain assumption Uniform random d-regular graph model G_d(n) for log^10 n << d = o(n)
- ad hoc to paper p-biased Fourier basis for G(n,d/n) is used as coordinates for graph matrices on regular inputs despite non-orthogonality
- ad hoc to paper The switched pseudo-calibration PSDness analysis can be completed from the new norm bounds
Cite this review
Pith. "Pith review of Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs." pith.science (2026). https://pith.science/paper/DK72BGAA
@misc{pith2026241114314,
author = {Pith},
title = {Pith review of: Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/DK72BGAA}},
note = {Machine review of arXiv:2411.14314}
}
abstract
In this work, we give novel spectral norm bounds for graph matrix on inputs being random regular graphs. Graph matrix is a family of random matrices with entries given by polynomial functions of the underlying input. These matrices have been known to be the backbone for the analysis of various average-case algorithms and hardness. Previous investigations of such matrices are largely restricted to the \Erdos-\Renyi model, and tight matrix norm bounds on regular graphs are only known for specific examples. We unite these two lines of investigations, and give the first result departing from the \Erdos-\Renyi setting in the full generality of graph matrices. We believe our norm bound result would enable a simple transfer of spectral analysis for average-case algorithms and hardness between these two distributions of random graphs. As an application of our spectral norm bounds, we show that higher-degree Sum-of-Squares lower bounds for the independent set problem on \Erdos-\Renyi random graphs can be switched into lower bounds on random $d$-regular graphs. Our result is the first to address the general open question of analyzing higher-degree Sum-of-Squares on random regular graphs.
Figures
Reference graph
Works this paper leans on
-
[1]
(Non-trivial middle-shape is bounded) For all sparse permissible τ that is a middle shape such that |V (τ )| > |Uτ |+|Vτ | 2 and |E(τ )| − |V (τ )| ≤Cdsos, λ′ τ · ∥Mτ ∥ |Aut(τ )| ≤ 1 c(τ ) for some defined slack function c(τ ) in [JPR+22] to be specified in later section,
-
[2]
(Intersection term is bounded) For all j ≥ 1 and sparse permissible γj, . . . , τ, . . . , γ′ j such that for each shape |Emid(α)| − |V (α)| ≤Cdsos, X nonequivalent P ∈P mid γj ,...,γ′ j NP (τP )λ′ γj ◦···◦γ′⊤ j ∥MτP ∥ |Aut(τP )| ≤ 1 c(τ ) Qj i=1 c(γi)c(γ′ i)
-
[3]
(Truncation error) truncation error ⪯ n−Ω(Cdsos)π
-
[4]
Verification of Non-trivial Middle Shapes Let us first unpack the lemma statement for the reader
(Well-conditionedness) (Sum of left shapes is well-conditioned) X sparse, permissible σ∈L λ′ σ Mσ |Aut(σ)| X sparse, permissible σ∈L λ′ σ Mσ |Aut(σ)| ⊤ ⪰ n−O(dsos)π We now proceed to verify key claims in the above conditions, and we leave the full verification to later versions of this paper. Verification of Non-trivial Mid...
-
[5]
Repeat this process until all vertices are pushed into W . Next we proceed to show this achieves our assignment goal, in particular, it assigns a phantom edge to a floating component. The proof on factors outside floating components is given in proof to Lemma 6.9 in [JPR+22] while we highlight the extra factor for the floating component here: this is anal...
-
[6]
S is a separator for τ, and by construction, Uτ and Vτ are both MVS of τ, therefore |S| ≥|Uτ |+|Vτ | 2 , therefore, we can assign a coefficient of k n for each vertex outside the separator
-
[7]
Each vertex is connected to Uτ and Vτ , and therefore the separator S by middle shape assumption, we can consider a BFS from S to traverse vertices outside the separator, and assign each vertex the edge (which comes with a coefficient of q p 1−p) that explores it in the process
-
[8]
Each vertex contributes a factor of ˜O(√n) and gets assigned a coefficient of k n · q p 1−p, and this is at most o(1) by our choice of k
Show all 17 references
-
[9]
Edges inside the separator give q 1−p p to the norm bound while it also comes with a coefficient of q p 1−p, which offsets each other. Verification with slack function We first recall the choice of slack function c(τ ) in [JPR+22] is chosen to be c(τ ) ≤ 40(2Cdsos4C′+2)|V (α)|...
-
[10]
VW ⊆ V (τP ): those reachable from W via edges in Eψ or already in W
-
[11]
For a connected component C ⊆ V (ψ) \ VW in Eψ while not yet reachable from W , it is either a non-floating component, or a floating component
-
[12]
We then consider the following process to assign phantom edges (i.e
For isolated vertices in V (ψ) \ VW , we can group them according to the phantom edges into compo- nents connected by phantom edges. We then consider the following process to assign phantom edges (i.e. those that become from mul ≥ 2 to 0 in ψ),
-
[13]
Let W be the current set of vertices visited (initialized to be S the SMVS of ψ)
-
[14]
Explore the vertices (not yet in W ) while connected to W via edges in E(ψ), i.e., assign the edge to each vertex it leads to
-
[15]
Explore a component connected to W via some phantom edge
-
[16]
For vertices outside W and not reachable via phantom from W , there must be a phantom-edge con- necting two different components, process that phantom edge and explore both components
-
[2018]
[KVWX23] Pravesh Kothari, Santosh S
Association for Computing Machinery. [KVWX23] Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, and Jeff Xu. Is planted coloring easier than planted clique? In Annual Conference Computational Learning Theory, 2023. [KWB19] Dmitriy Kunisky, Alexander S. Wein, and Afonso S...
2023 arXiv
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.