{"id":"77900e3e-90a7-4d09-a6d6-8322541f9e95","arxiv_id":"2608.03848","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A bound on the second biadjacency singular value alone certifies FPRAS counting and polynomial-time sampling for the hard-core model at every fugacity on Δ-regular bipartite graphs.","lead":"New algorithms count and sample hard-core model independent sets on Δ-regular bipartite graphs whenever the second singular value of the biadjacency matrix is small enough. A single efficiently checkable spectral certificate now covers all fugacities, where previous all-fugacity results held only for random graphs with high probability.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2's bound (4.9) is off by a factor of Δ²: substituting r=n/Δ, |V|=2n, h≥Δ/4, MLE=Δ gives 2Δ³/h ≥ 8Δ², not ≤8. The HP26 condition is therefore not verified, so the high-fugacity threshold and all-fugacity overlap collapse.","rationale":"The reader identified reliance on external black-box theorems as the weakest assumption. My stress-test sharpens this to a concrete internal inconsistency in the verification of one of those black boxes. Section 4.1, specifically inequality (4.9), claims a bound that does not follow from the definitions stated in Section 2.2 and Proposition 2.5. This is a load-bearing step: Lemma 4.2 establishes phase dominance, Lemma 4.4 uses it to bound the polymer-model error, and Theorem 1.3's fugacity threshold is then matched with Theorem 1.2's moderate range in the proof of Theorem 1.1. If the asymptotic threshold is actually exp(Ω(Δ)) rather than exp(O(σ²/Δ² log Δ)), the proposed all-fugacity guarantee fails, because the moderate regime only reaches λ ≈ 1/σ while the high-fugacity regime only starts exponentially far above. I did not find a comparable flaw in the moderate-fugacity localization argument: Lemma 3.1's dependency-matrix computation checks out, the mixture identity and truncation are internally consistent, and the annealing arguments are sound modulo the usual dependence on Δ. The paper also deserves credit for a clear algorithmic framework and for making the spectral certificate efficiently checkable. But the high-fugacity proof, as written, contains a quantitative step that is false under the paper's own definitions. Because this step is required for the central all-fugacity theorem, the verdict should move from CONDITIONAL to REJECT. I frame the check around re-deriving (4.9) and consulting the original HP26 statement, since the fix may be a misquotation rather than an unfixable flaw; either way, the current manuscript does not establish the theorem.","tokens_in":22784,"tokens_out":33124,"duration_ms":343997,"concrete_test":"Recompute (4.9) using the manuscript's own definitions: r=n/Δ, |V(G)|=2n, h(G)≥(Δ−σ)/2, M_LE=Δ. For σ≤Δ/2 this yields Δ/h·|V|/r·M_LE ≥ 8Δ², not ≤8. Then consult the original [HP26, Theorem 1.7] and check the exact second term in the max: if it is Δ/h·|V|/r·M_LE, Lemma 4.2 is false; if it is instead Δ/h·|V|/r/M_LE (or has an extra 1/Δ factor), verify that the corrected HP26 statement is what the paper intended and recompute the high-fugacity threshold. If the corrected threshold is exp(Ω(Δ)), rerun the overlap argument in Theorem 1.1 with that threshold; it will not overlap with the moderate regime when σ ≈ c(Δ²/log Δ)^{1/3}.","verdict_should_be":"REJECT","load_bearing_attack":"The proof of Theorem 1.3, and hence the all-fugacity Theorem 1.1, depends on Lemma 4.2's verification of the Hadas–Peled hypothesis. In (4.9), the paper claims Δ/h(G) · |V(G)|/r · M_LE ≤ 8. But with the paper's own definitions, r = n/Δ, |V| = 2n, h(G) ≥ Δ/4 (from Lemma 2.2), and M_LE = Δ (from Proposition 2.5), the left side is (Δ/h)·(2Δ)·Δ ≤ 4·2Δ·Δ = 8Δ², which is Δ² times larger than 8. This is not a small typo: if (2.10) is taken literally, the second term inside the max is Θ(Δ²) (or worse), so the high-fugacity threshold becomes exp(Ω(Δ)) instead of the claimed exp(O((1/Δ + σ²/(Δ²−σ²)) log(eΔ))). Then the moderate-fugacity range λ ≤ 1/(2σ) and the high-fugacity range λ ≥ exp(Ω(Δ)) do not overlap, and Theorem 1.1's parameter matching fails. The only way the argument survives is if the quoted HP26 condition is a mistranscription and the original theorem has a smaller second term (e.g., involving 1/M_LE or an extra 1/Δ factor); the paper does not provide that. Thus, as written, the phase-dominance step is unsupported, and the central claim does not follow.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies approximate counting and sampling for the hard-core model on Δ-regular bipartite graphs under a spectral expansion condition. Let M_G be the biadjacency matrix and σ_2(M_G) its second singular value. The main result (Theorem 1.1) asserts that if σ_2(M_G) ≤ c(Δ²/log(eΔ))^{1/3}, then there is an FPRAS for the hard-core partition function and an efficient approximate sampler at every fugacity λ>0. The proof splits into two regimes. For moderate fugacity (Theorem 1.2), the authors introduce a family of quadratically tilted measures on the left-right imbalance, prove spectral independence for these tilted measures via the dependency-matrix criterion of [CCC+25], and use an exact discrete Hubbard–Stratonovich identity to express the hard-core model as a positive mixture of tilted measures. For high fugacity (Theorem 1.3), they refine the polymer-model approach: a Hadas–Peled long-range-order theorem gives phase dominance, and a Tanner-inequality-based verification of the Kotecký–Preiss condition gives convergent cluster expansions. The two fugacity ranges are matched to cover all λ>0.","tokens_in":23179,"tokens_out":45810,"duration_ms":500946,"significance":"If correct, the result is significant: it gives a single efficiently checkable spectral certificate for all-fugacity approximate counting and sampling on a natural class of bipartite expanders, recovering the previous random-regular-bipartite results and adding a certifying guarantee. The discrete quadratic localization technique is new and the mixture identity is exact and self-contained; there are no fitted parameters. The proof depends on two external black-box theorems ([CCC+25, Theorem 1.9] and [HP26, Theorem 1.7]); the manuscript verifies their hypotheses but does not prove the theorems themselves. I found no circularity or parameter fitting. The main caveat is a proof gap in the FPTAS guarantee at high fugacity, discussed below, which is repairable.","major_comments":[{"comment":"The polymer-model approximation has an intrinsic bias: eZ_G(λ) := (1+λ)^n(Ξ_L+Ξ_R) satisfies eZ_G - Z_G = W_∩ - W_∅. Lemma 4.4 bounds (W_∩+W_∅)/Z_G by (2n+2) exp(-c n log(eΔ)/Δ²). For n = Θ(Δ²) and fixed Δ, this bound is a constant independent of n, not a quantity that can be made smaller than an arbitrarily small ε by running the algorithm longer. As written, the proposed FPTAS approximates eZ_G and does not control this bias to level ε for all ε. To obtain the stated FPTAS guarantee, the proof must add an exact enumeration branch when n is below an ε-dependent threshold (roughly n ≲ (Δ²/log Δ) log(1/ε)); for fixed Δ this is polynomial in 1/ε. The same issue affects the sampler's total-variation guarantee in Lemma 4.8. The claim is repairable, but the current text does not supply this step.","section":"§4, Lemma 4.4 and proof of Theorem 1.3"}],"minor_comments":[{"comment":"In the proof of Lemma 3.1, after substituting √(r_L r_R) = t√q, the off-diagonal coefficient is -t q^{-1/2} E_S, not -t√q E_S. The displayed bound should read 2t q^{-1/2}|x^T E_S y| and tσ q^{-1/2}(||x||²+||y||²), not tσ√q. The consequence δ = 1 - tσ/√q is consistent with the corrected bound, so the error is local, but (3.6) as printed is not implied by the displayed algebra.","section":"§3.1, Lemma 3.1"},{"comment":"The prose states that for two available vertices on the same side Ψ_S(u,v) = q^{-1}-1. The correct value is q-1 = -a, which is what the matrix in (3.7) uses. Please fix the prose to match the matrix.","section":"§3.1, proof of Lemma 3.1"},{"comment":"The expression rMLE should be typeset as a denominator, i.e. r M_LE, in both (2.10) and (4.9). If read as a product in the numerator, the bound (4.9) is off by a factor Δ²; with M_LE in the denominator it is exactly 8 under the paper's definitions. The ambiguity should be removed in the final version.","section":"§2.2 and §4.1, (2.10) and (4.9)"},{"comment":"The proof of Theorem 1.3 assumes n ≥ Δ² (see Lemma 4.2). The theorem statement and Section 4 should explicitly state the enumeration case for n < Δ², and also the ε-dependent small-n case needed for the FPTAS guarantee discussed in the major comment.","section":"§4"},{"comment":"The fugacity threshold in (1.4) uses only σ²/(Δ²-σ²), while the proofs of Lemmas 4.2 and 4.9 use 1/Δ + σ²/(Δ²-σ²). This is harmless when n ≥ Δ² by Lemma 2.1, but the equivalence should be stated explicitly to avoid an apparent mismatch.","section":"Theorem 1.3 statement"}],"recommendation":"major_revision","confidential_remarks":"The manuscript relies heavily on two unpublished preprints, [CCC+25] and [HP26]. If the journal requires black-box results to be published or thoroughly verified, this is a risk; the authors verify only the hypotheses, not the theorems. The self-citations [NPWW26] and [GJM+26] are contextual and not load-bearing. The stress-test concern about (4.9) does not land if M_LE is read as part of the denominator, which is how the displayed equation appears; I have asked for a notation fix. Overall the paper is well within scope, but the FPTAS/sampler bias issue in Section 4 should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me get straight to it. This is a strong paper with one load-bearing thing to check before trusting it. The genuinely new part is discrete quadratic localization: tilt independent sets by q^{f(m)+km}, use a discrete Gaussian/Hubbard–Stratonovich identity to write Z_G(t) as an exact positive mixture over k, and show the tilted measures mix rapidly from a sigma_2 bound alone. That half is clean, self-contained, no fitted parameters. It gives an efficiently verifiable spectral certificate for moderate fugacity, which is a real improvement over what KOGT26 and JKP20 do for random graphs. The high-fugacity polymer argument follows the standard JKP20/CGSV22 template, but the novelty is deriving long-range order and the Kotecky–Preiss condition from sigma_2.\n\nNow the soft spot. The stress-test note is correct on the printed text. The quoted Hadas–Peled condition (2.10) has second term (Delta/h)(|V|/r) M_LE. In Lemma 4.2, with r=|V|/(2Delta), |V|/r=2Delta, h>=Delta/4, M_LE=Delta, that term is up to 8Delta^2, not <=8. So if (2.10) is right, (4.9) proves the wrong inequality, and the high-fugacity threshold becomes exp(Omega(Delta)) — no overlap with the moderate range, and Theorem 1.1 falls. However, the paper's own bound in (4.9), namely <=8, is exactly what you get if the second term were (Delta/h)(|V|/r)/M_LE. So my guess is that (2.10) is a mistranscription of HP26, and the authors verified the correct condition. But as written, the proof applies a theorem it does not actually check. A referee has to pull HP26 and settle which form is right. This is not cosmetic; it is the load-bearing step. It also looks very fixable.\n\nOther issues are minor. There is a sign typo in the same-side dependency display (q^{-1}-1 for q-1); the matrix right after uses the correct value. The reliance on CCC+25 and HP26 as black boxes is fine, since the hypotheses are clearly stated in the moderate-fugacity half, modulo the HP mismatch.\n\nBottom line: if the HP condition is what (4.9) verifies, this is a significant advance in the expander counting program. The paper deserves a serious referee; I would not desk reject. It needs a revision that quotes HP correctly and re-checks the constant chase. I would bring it to reading group — the localization idea alone is worth people seeing.","headline":"Genuinely new localization technique; the high-fugacity half hinges on a likely typo in the quoted Hadas–Peled condition that must be checked before the all-fugacity claim stands.","tokens_in":737,"tokens_out":917,"would_cite":true,"duration_ms":88569,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that one spectral bound on the biadjacency matrix of a high-degree regular bipartite graph guarantees efficient approximate counting and sampling for the hard-core model at every fugacity.","keywords":["hard-core model","independent sets","approximate counting","approximate sampling","Glauber dynamics","spectral expansion","bipartite graphs","polymer models"],"falsifier":"Take a family of Δ-regular bipartite graphs whose second singular value meets the bound and set λ=1/(2σ2); if the single-site Glauber dynamics for the quadratically localized measure with k=0 mixes in time exponential in n, the moderate-regime half of the theorem is false. For the high-fugacity half, seek an independent set with more than n/Δ vertices on both sides whose weight exceeds the bound in Lemma 4.2 at the stated λ; such a set would falsify the long-range-order claim.","tokens_in":22656,"feed_emoji":"🧮","tokens_out":7422,"duration_ms":81575,"temperature":0.7,"pith_summary":"The paper proves that a purely spectral condition on a bipartite graph's biadjacency matrix—a small second singular value—certifies that the hard-core model (the distribution on independent sets weighted by λ^{|I|}) can be approximately counted and sampled at every fugacity λ>0, on high-degree regular graphs. At moderate λ it introduces tilted measures that penalize left-right occupation imbalance; their Glauber dynamics mix rapidly, and an exact discrete Gaussian identity reconstructs the original hard-core partition function as a positive mixture of the tilted ones. At high λ it shows that polymer-model phase dominance and cluster-expansion convergence follow from the same spectral bound, via a scale-sensitive Tanner inequality. If the theorem is right, this yields deterministic, efficiently checkable all-fugacity algorithms for a broad class of bipartite expanders and recovers earlier random-graph results as a special case. It matters because counting independent sets in bipartite graphs (#BIS) is a central open problem, and this identifies a broad regime where it becomes easy.","feed_headline":"One spectral number certifies hard-core counting at every fugacity","feed_subtitle":"When a bipartite graph's biadjacency matrix expands, one check gives efficient counting and sampling for every λ>0.","key_machinery":"The central object is the quadratically localized measure µ_{G,t,k}(I) ∝ t^{|I|} q^{f(m(I))+km(I)}, with q=1−Δ/n, f(a)=a²/2, and m(I)=|I∩L|−|I∩R|; a discrete Gaussian identity, Z_G(t)=Σ_k p_k Z_{G,k}(t) with p_k∝q^{k²/2}, expresses the hard-core partition function as an exact positive mixture. In the high-fugacity regime the load-bearing tools are the two-phase polymer models with weights λ^{|S|}/(1+λ)^{|N(S)|}, the scale-sensitive Tanner inequality |N(S)|/|S| ≥ Δ²/(σ²+(Δ²−σ²)|S|/n), and the Hadas–Peled long-range-order criterion.","core_discovery":"The central claim is Theorem 1.1: there are absolute constants c>0 and Δ0 such that for every Δ≥Δ0, every Δ-regular bipartite graph with second singular value σ2(M_G)≤c(Δ²/log(eΔ))^{1/3} has an FPRAS for the hard-core partition function and an efficient approximate sampler at every fugacity λ>0. The proof establishes the moderate-fugacity range λ≤(1−ξ)/σ by showing that each quadratically localized measure has a controlled dependency matrix and hence rapidly mixing Glauber dynamics, and that the original partition function is an exact positive mixture of these localized partition functions. For the complementary high-fugacity range, it verifies the Hadas–Peled long-range-order criterion and","pith_inferences":["Editorial inference: the quadratic-localization mechanism is not obviously specific to hard-core; the same 'cancel the rank-one direction' idea could plausibly extend to other two-spin antiferromagnetic models on bipartite expanders.","Editorial inference: the exponent 1/3 in the spectral threshold is likely not the true frontier; sharpening the high-fugacity overlap analysis may push the certificate toward σ=O(√Δ), matching Ramanujan graphs.","Editorial inference: because the certificate is a single singular value, it can be checked in near-linear time, making the theorem practically usable as a preprocessing test before running the algorithms.","Editorial inference: the paper does not address what happens outside the spectral bound; a natural test is whether the tilted-measure Glauber dynamics still mixes rapidly when σ is just above the stated threshold."],"forward_implications":["For every Δ-regular bipartite graph meeting the spectral bound, the hard-core partition function can be approximated to relative error ε and samples drawn to total-variation error ε in time polynomial in n and 1/ε, for every λ>0.","Uniformly random Δ-regular bipartite graphs satisfy the spectral condition for large Δ, so the all-fugacity algorithms apply with a certificate checkable on the given graph rather than only with high probability over the random construction.","The moderate-fugacity theorem gives FPRAS and efficient sampling for λ=O(1/σ) on every graph in the spectral class, matching the range previously known only for random regular bipartite graphs.","The high-fugacity theorem delivers FPTAS and efficient sampling for λ≥exp(C σ²/(Δ²−σ²) log(eΔ))−1, with cluster-expansion convergence following from the singular-spectrum bound alone."],"supporting_citations":[{"why":"Supplies the dependency-matrix rapid-mixing criterion (Theorem 2.7) used to certify Glauber dynamics for the tilted measures.","marker":"[CCC+25]"},{"why":"Supplies the long-range-order theorem (Theorem 2.6) used to establish phase dominance in the high-fugacity regime.","marker":"[HP26]"},{"why":"Supplies the two-phase polymer-model framework and the algorithmic cluster-expansion criteria that the high-fugacity algorithms build on.","marker":"[JKP20]"},{"why":"Refines the polymer-model approach for random regular bipartite graphs and gives the strongest previous high-fugacity guarantees that the spectral analysis improves on.","marker":"[CGŠV22]"},{"why":"Handles the moderate-fugacity regime for random regular bipartite graphs with auxiliary chains, the benchmark the spectral moderate-fugacity result matches deterministically.","marker":"[KOGT26]"},{"why":"Provides the scale-sensitive Tanner inequality used to control neighborhood growth of polymers and to verify the Kotecký–Preiss condition.","marker":"[Tan84]"},{"why":"Provides the Cheeger-inequality form used to lower-bound edge expansion from the second singular value.","marker":"[HLW06]"},{"why":"Uses Hubbard–Stratonovich integration of unfavorable eigen-directions in Ising sampling, the closest methodological antecedent for quadratic localization.","marker":"[KLR22]"}],"fun_headline_variants":["One spectral number unlocks hard-core counting at all fugacities","Single σ2 bound certifies FPRAS for every hard-core fugacity","Bipartite spectral expansion: one check for all-λ algorithms","Hard-core model: one singular value gates counting and sampling"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that the two external theorems it invokes—the rapid-mixing criterion for Glauber dynamics and the Hadas–Peled long-range-order theorem—apply without hidden restrictions to the tilted and polymer constructions used here; the paper checks their hypotheses but does not prove the theorems themselves.","fun_headline_variants_meta":{"raw":{"variants":["One spectral number unlocks hard-core counting at all fugacities","Single σ2 bound certifies FPRAS for every hard-core fugacity","Bipartite spectral expansion: one check for all-λ algorithms","Hard-core model: one singular value gates counting and sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1360,"prompt_tokens":833,"completion_tokens":527,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":453}},"tokens_in":577,"tokens_out":527,"duration_ms":7011,"temperature":1.0,"reasoning_tokens":453,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:08:28.542061+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a family of Δ-regular bipartite graphs whose second singular value meets the bound and set λ=1/(2σ2); if the single-site Glauber dynamics for the quadratically localized measure with k=0 mixes in time exponential in n, the moderate-regime half of the theorem is false. For the high-fugacity half, seek an independent set with more than n/Δ vertices on both sides whose weight exceeds the bound in Lemma 4.2 at the stated λ; such a set would falsify the long-range-order claim.","supporting_citations":[],"review_version":1}