{"id":"50e5be72-2499-4d74-8291-404e67bc0a52","arxiv_id":"2411.14314","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New norm bounds for graph matrices on random d-regular graphs are proven, yielding a stated switch of Sum-of-Squares lower bounds from Erdős-Rényi to regular graphs, with the switch proof deferred.","lead":"This paper gives spectral norm bounds for graph matrices on random regular graphs, with an extra √n factor for each tree-like floating component, and uses them to state first higher-degree Sum-of-Squares lower bounds for independent set on regular graphs. The norm bound proof is detailed, but the Sum-of-Squares application relies on a PSDness analysis the paper explicitly defers to a later version.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central SoS lower-bound claim (Theorem 3.4) depends on the PSDness lemmas of Appendix A, whose full verification is explicitly deferred ('we leave the full verification to later versions of this paper'); the switching theorem is therefore not established as stated.","rationale":"Reading the paper in good faith: the contribution is twofold — (i) graph matrix norm bounds for random d-regular graphs in the dense regime with a floating-component characterization, and (ii) a switching theorem giving the first higher-degree SoS lower bound for independent set on G_d(n). Section 2 is a genuine technical development: it adapts the block-value machinery to Sarid's regular-graph edge-value bound, and the floating-component definition correctly captures the sqrt(n) blow-up visible in scalar examples. But the advertised headline is Theorem 3.4, and that theorem requires the pseudo-calibration moment matrix to be PSD. The proof of PSDness is not in the paper. Appendix A explicitly says 'we leave the full verification to later versions of this paper'; the four conditions of Lemma A.1 are only sketched. The most delicate of these is the intersection-term bound, where tree-like floating components appear and must be charged to phantom edges. Proposition A.5's inequality (2) is asserted with a traversal argument, but the key claim that a phantom edge's 'second multiplicity remains unassigned' is not proven. If that charging fails, the PSDness of the switched pseudo-distribution may fail, and the lower bound would not hold. This is an internal incompleteness, not a disagreement with consensus: the paper itself identifies the missing verification. The reader's weakest_assumption matches this exactly. I therefore see no reason to change the REJECT verdict; I would note that acceptance would be appropriate if the PSDness lemmas are completed and the charging argument verified, particularly for the tree-like floating components in intersection terms.","tokens_in":26289,"tokens_out":4251,"duration_ms":38535,"concrete_test":"Complete the deferred PSDness verification for the intersection-term condition (Lemma A.1, item 2) on a minimal concrete case: take a left shape gamma, middle shape tau, and right shape gamma-prime such that some linearization psi of the composed intersection shape tau_P has a tree-like floating component, and check the claimed charging inequality |E_psi| + phantom(psi) >= |V(tau_P) \\ V(S)| + |E_psi(S)| + |I_psi| + |float_psi| with the actual shape coefficients lambda-prime and slack function c(tau). Concretely, verify that the 'second multiplicity' of each phantom edge is not simultaneously needed to pay for a first vertex outside S, and that the inequality holds with the constants in the slack function. If this fails for any sparse permissible intersection pattern, Theorem 3.4 does not follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the pseudo-expectation's PSDness. Theorem 3.4 is obtained by taking the [JPR+22] pseudo-calibration moment matrix (Definition 3.8) and plugging in random regular inputs; the independent-set and objective-value constraints (Claims 3.12, 3.13) are verified, but the moment matrix must be PSD. That PSDness is exactly Lemma A.1, comprising non-trivial middle shapes, intersection terms, truncation error, and well-conditionedness. Appendix A does not prove these lemmas: it states 'we leave the full verification to later versions of this paper' after sketching the middle-shape case and the intersection-term case (Proposition A.5). The delicate point is the latter: unlike middle shapes, intersection shapes can develop tree-like floating components after edge-removal (linearization), and the paper's norm bound then incurs a sqrt(n) blow-up per floating component, which must be charged to a 'phantom' edge whose multiplicity changes from at least 2 to 0. Proposition A.5 asserts the key inequality |E_psi| + phantom(psi) >= |V(tau_P) \\ V(S)| + |E_psi(S)| + |I_psi| + |float_psi| and claims that 'the second multiplicity remains unassigned' and can pay for the floating-component blow-up. This charging argument is not a routine specialization of [JPR+22]: it is precisely where the regular-graph norm bounds and the connected-truncation interaction matter. No complete derivation is given for the slack-function version, for the truncation error, or for well-conditionedness, each of which is asserted to follow 'immediately' or 'verbatim.' Because the abstract and Theorem 3.4 present the SoS lower bound as established, the absence of a complete PSDness proof is a load-bearing correctness gap, not a presentation issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":26465,"tokens_out":9811,"duration_ms":83302,"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":[{"comment":"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.","section":"Appendix A, Lemma A.1"},{"comment":"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.","section":"Appendix A, Proposition A.5"},{"comment":"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.","section":"Lemma 2.27 and its use in Theorem 2.10"},{"comment":"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.","section":"Theorem 2.9, Proposition 2.29, and Theorem 3.4"}],"minor_comments":[{"comment":"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.","section":"Section 2.2, Theorems 2.9 and 2.10"},{"comment":"The definition of floating component says 'no path from C to Uτ ∪ Vα'; this should be Vτ.","section":"Definition 2.7"},{"comment":"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.","section":"Example 3.6"},{"comment":"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.","section":"Remark 3.7"},{"comment":"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.","section":"Lemma 2.18 and Proposition 2.19"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is an early preprint that explicitly defers the main PSDness analysis of Appendix A to a later version. Given that this appendix is the core of the SoS application, the paper is not in a publishable state as submitted. The norm-bound section alone could be a solid contribution if the sketched charging arguments in Section 2 are tightened and the d-range/concentration issue is resolved, but the current version should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The norm bounds are a real contribution: first full-generality graph matrix bounds for G_d(n), and the floating-component √n blow-up is a genuinely new structural idea that seems right. The adaptation of Sarid's edge-value bound into the block-value framework is natural and mostly solid; Section 2 is plausible and, modulo some sketched charging arguments, looks fixable.\n\nThe problem is the advertised application. Theorem 3.4 is the headline, and its PSDness proof is load-bearing. Appendix A explicitly says 'we leave the full verification to later versions of this paper' after sketching the middle-shape and intersection-term cases. Proposition A.5 asserts the key inequality |E_ψ| + phantom(ψ) ≥ |V(τ_P) \\ V(S)| + |E_ψ(S)| + |I_ψ| + |float_ψ| — exactly where the regular-graph norm bounds and the connected truncation interact. This is not a routine specialization of JPR+22; it is where the √n blow-up from floating components is supposed to be charged to phantom edges. The slack-function version, truncation error, and well-conditionedness are each asserted to follow 'immediately' or 'verbatim.' That is a correctness gap, not a presentation issue, and the abstract sells the switching result as established.\n\nThe author is honest about some limitations, including the heuristic distinguisher bound in Example 3.6 and the Kim-Vu sandwich remark in the acknowledgement, but that does not make the central theorem proven.\n\nWho gets value: researchers in SoS lower bounds and graph matrix theory. The floating-component phenomenon is a useful conceptual lesson for transferring between G(n,p) and G_d(n). But the current paper should not be accepted as is. It needs either the PSDness analysis completed or a reframing as a norm-bounds-only paper with the SoS application as a conjecture.\n\nRecommendation: send it to a serious referee, because the norm-bound contribution deserves scrutiny and the open question is important. My own verdict on this version is reject-and-revise: the main theorem is not established as stated.","headline":"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.","tokens_in":27174,"tokens_out":2403,"would_cite":true,"duration_ms":24086,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","68Q17","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"First higher-degree SoS lower bounds on random regular graphs","keywords":["graph matrices","spectral norm bounds","random regular graphs","Sum-of-Squares lower bounds","independent set problem","block-value method","floating components","pseudo-calibration"],"falsifier":"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.","tokens_in":25877,"feed_emoji":"🧮","tokens_out":8706,"duration_ms":74497,"temperature":0.7,"pith_summary":"This paper attempts to transfer spectral norm bounds for graph matrices from Erdős–Rényi random graphs $G(n,d/n)$ to uniformly random $d$-regular graphs $G_d(n)$, and then uses that transfer to carry over higher-degree Sum-of-Squares lower bounds for the independent set problem. The target theorem is the first higher-degree SoS lower bound on random regular graphs: for $k \\le \\frac{n}{\\sqrt d} \\cdot \\frac{1}{d_{\\mathrm{sos}}^{c_1}\\log n}$, a degree-$d_{\\mathrm{sos}}$ pseudo-expectation with objective value $(1-o(1))k$ exists with high probability when $d_{\\mathrm{sos}}<d^{1/10}$. The proof hinges on new norm bounds that differ from the i.i.d. case only when the shape contains a tree-like 'floating' component, which costs an extra $\\sqrt n$ factor; the application shows that the SoS analysis only meets such components in intersection terms where their extra cost is covered by slack. The PSDness verification is sketched in an appendix and explicitly deferred to a later version.","feed_headline":"First higher-degree SoS lower bounds on random regular graphs","feed_subtitle":"New norm bounds carry the Erdős–Rényi independent-set hardness proof over to regular graphs.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Erdős–Rényi Sum-of-Squares lower bound for sparse independent set and the PSDness framework (middle shapes, intersection terms) that the paper switches to $G_d(n)$.","marker":"[JPR+22]"},{"why":"Provides the edge-value bound for shape walks in random regular graphs (Lemma 2.18) that replaces i.i.d. factorization in the norm-bound proof.","marker":"[Sar23]"},{"why":"Contributes the optimized block-value machinery and step-labeling factor assignment from the sparse i.i.d. setting that the paper adapts.","marker":"[KPX24]"},{"why":"Establishes the pseudo-calibration plus PSD analysis template that the SoS lower bound construction follows.","marker":"[BHK+16]"},{"why":"Gives the general graph-matrix norm-bound framework and block-value formalism that underpins the proof.","marker":"[AMP20]"}],"fun_headline_variants":["New norm bounds unlock SoS lower bounds on regular graphs","Regular graphs get first SoS lower bounds via new norm estimates","Graph matrix norm bounds enable SoS lower bounds on regular graphs","Spectral norm bounds transfer SoS hardness to regular graphs","From Erdos-Renyi to regular: SoS hardness via new norms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New norm bounds unlock SoS lower bounds on regular graphs","Regular graphs get first SoS lower bounds via new norm estimates","Graph matrix norm bounds enable SoS lower bounds on regular graphs","Spectral norm bounds transfer SoS hardness to regular graphs","From Erdos-Renyi to regular: SoS hardness via new norms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00273,"raw_usage":{"total_tokens":10417,"prompt_tokens":960,"completion_tokens":9457,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":9370}},"tokens_in":576,"tokens_out":9457,"duration_ms":55756,"temperature":1.0,"reasoning_tokens":9370,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:19:19.930172+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}