{"id":"b6e01bec-c41e-4e2c-a5cd-974cbedf14c4","arxiv_id":"2608.02503","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The balanced hard-core model on bounded-degree bipartite graphs has the same computational threshold as the ordinary hard-core model, and certain fixed-density slices are NP-hard to approximate.","lead":"This paper proves that counting and sampling balanced independent sets in bounded-degree bipartite graphs is exactly as hard as counting hard-core independent sets: easy below the tree uniqueness threshold, impossible (unless NP=RP) above it. It also identifies fixed-size slices of bipartite independent sets that are NP-hard to approximately count or sample.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Hardness rests on Lemma 4.3's pointwise terminal-law bounds imported from [18,19]; if those bounds do not cover the exact growing-terminal gadget with m=n^theta terminals, the compatibility-factor calculation in Sections 4.3/5 breaks.","rationale":"The paper's positive algorithm below lambda_c is substantial and mostly self-contained; I checked the tilted SSM contraction, the zero-freeness/local CLT route, and the FPTAS assembly, and the argument is coherent. One minor internal note: Eq. (2.6) appears to have a typo (the factor y0/(1+y0) should be squared under the radical), but the subsequent derivation of Theta_{a,b,lambda} in (2.15) uses the correct derivative square, so the contraction proof's substantive calculation is consistent. The load-bearing uncertainty is the hardness side: Lemma 4.3 is inherited rather than proved, and the pointwise terminal-law estimate (3) is exactly what converts the gadget phase vector into the cut objective. The reader's weakest_assumption identified this same point, and I agree. Because this is a standard import that prior work is designed to supply, and because no concrete failure has been demonstrated, I do not change the ACCEPT verdict; however, the proposed check would either remove the residual doubt or force a conditional/reject re-evaluation.","tokens_in":55685,"tokens_out":47855,"duration_ms":474039,"concrete_test":"Check the exact statements of [19, Lemmas 19 and 23] and [18, Theorem 1.4, Lemma 3.2] to confirm they imply (3) pointwise for all 2^{2m} terminal configurations with m=floor(n^theta), theta in (0,1/8), on the tree-augmented gadget, not merely total-variation closeness or a constant number of terminals. Re-derive the second-moment/small-subgraph estimate for the exact single-gadget terminal law and verify the relative error n^{-2theta} is uniform in tau. As a complementary numerical probe, for Delta=3, n=2^10, theta=0.1, compute the terminal law by transfer-matrix enumeration and compare max_tau |mu(tau)/Q(tau)-1| with n^{-2theta}.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The pivotal, least-secure condition is Lemma 4.3, specifically the pointwise estimate (3): for every tau in {0,1}^T and both phases, mu_{G,sigma}(sigma_T=tau)/Q^sigma_T(tau) = 1 + O(n^{-2theta}), together with the polynomial-factor bounds (6)-(8). These are imported from Galanis-Stefankovic-Vigoda [18,19] and are not re-proved for the exact tree-augmented gadget of Section 4.1 (m=floor(n^theta) terminals per side, degree-Delta core plus depth-d_n trees). The whole Section 4.3 uses (3) to replace the true terminal law by the product law Q^Y_T in both upper and lower bounds, producing the exact inter-gadget factor Gamma^{2k|E(H)|}(Theta/Gamma)^{2k cut(Y)}, and uses (6)-(8) to compare Z_{bH_G}(Y*) with Z_{bH_G} within e^{O(h log n)}. If the cited lemmas give only total-variation closeness, or require a fixed number of terminals, then for exponentially rare tau the ratio can be far from 1 and the factored compatibility weight is unjustified. The fixed-slice reduction in Section 5 inherits this and adds terminal-conditioned moment estimates (Lemma 4.4), so both hardness directions of Theorems 1.1 and 1.2 sit on this imported lemma. I do not have a counterexample; this is where correctness risk concentrates.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two conditional hard-core models on bipartite graphs of maximum degree Δ with equal side sizes: fixed-slice independent sets with prescribed densities (α_L, α_R), and balanced independent sets with |I∩L|=|I∩R|. Theorem 1.1 proves that for α=(α_L+α_R)/2 ∈ (1/Δ, 1/2) and side densities more balanced than the phase-aligned ratios, FixedSlice(α_L, α_R) has no FPRAS and no efficient sampling scheme unless NP=RP. Theorem 1.2 proves that the balanced model has the same computational threshold as the hard-core model on bounded-degree graphs: an FPTAS and efficient sampler below λ_c(Δ), and no FPRAS or efficient sampler above λ_c(Δ) unless NP=RP. The algorithmic side is based on a tilted hard-core model, strong spatial mixing on the SAW tree, zero-freeness, and a local central limit theorem; the hardness side uses random bipartite phase-coexistence gadgets and reductions from MIN-BISECTION and γ-MEBC.","tokens_in":56075,"tokens_out":23780,"duration_ms":250033,"significance":"If correct, these results give a clean worst-case threshold for the balanced hard-core model on bounded-degree bipartite graphs, matching the general hard-core threshold, and provide the first fixed-slice hardness results in the bipartite setting, showing that slice-decomposition does not by itself circumvent #BIS-hardness. The paper is unusually detailed: the two-level contraction proof for tilted SAW trees (Theorem 2.8), the zero-freeness result (Proposition 2.15), and the deterministic FPTAS in Section 3 are substantial technical contributions. The hardness framework is explicit, with careful terminal-compatibility calculations. The main caveat is that Lemma 4.3 imports pointwise phase estimates from [18,19] rather than reproving them in the exact tree-augmented gadget; this is a verification burden, not an internal inconsistency, and the manuscript states the specific transfer.","major_comments":[],"minor_comments":[{"comment":"The hardness theorems rest on the imported pointwise estimates (3)–(8). The paper gives a proof sketch and cites [18, Proof of Lemma B.3] and [19, Lemmas 19/20/23, Section 7.2.1], but the reductions in §4.3 and §5 use the exact pointwise terminal-law ratio and the polynomial factor bounds. Since this is load-bearing, I recommend adding a short appendix or precise theorem statements reproducing the transfer to the tree-augmented gadget, or at least quoting the exact statements from [18,19]. This would remove the main verification burden without changing the results.","section":"§4.1, Lemma 4.3"},{"comment":"The paper is transparent that the algorithm is proved only for bipartition ratios within a constant factor γ of balanced, and that unbalanced ratios are left open. This is not a defect for the stated theorem, but it would be helpful to note explicitly that Theorem 1.2 only claims equal side sizes, so the remark is simply an honest limitation of the stronger Proposition 2.1.","section":"§2, Remark 2.2"},{"comment":"The paper honestly notes that the fixed-slice hardness boundary may be an artifact of the proof and leaves the complementary region open. This is a useful pointer for future work, and the language is appropriately cautious.","section":"§1.2, Problem 1.4"},{"comment":"Minor typos: 'abbreviated:= ∆−1' should be 'write d := ∆−1'; the notation λ†(u)(ζ) is used before being defined; and the heading 'Proof of Proposition 2.9.' appears twice. These should be cleaned up before publication.","section":"§2.2, Proof of Theorem 2.8"},{"comment":"In the proof of Proposition 2.15, the case δ ≥ λ_c(Δ) is dismissed as making the interval for λ empty. More precisely, the condition λ ∈ (0, λ_c−δ) is empty, so this is fine, but the sentence could be clarified to avoid confusion.","section":"§2.4, Proposition 2.15"}],"recommendation":"minor_revision","confidential_remarks":"The paper is sound in its internal logic, and the algorithmic side is essentially self-contained. The hardness side inherits a substantial gadget-analysis from prior work; if the editor wants a stronger guarantee, the authors should be asked to include the precise imported statements. The unusual 'Statement of AI use' is a disclosure and does not affect my assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a substantial paper and I think it deserves a serious referee. It proves two genuinely new computational threshold results for the hard-core model on bipartite graphs under global constraints, and it adapts known machinery without, as far as I can tell, fitting anything.\n\nWhat is new: Theorem 1.2 shows the balanced hard-core model (conditioned on |I∩L|=|I∩R|) has the same FPTAS/efficient sampling region λ<λ_c(Δ) and the same hardness region λ>λ_c(Δ) as the unconstrained model on bounded-degree graphs. The algorithmic half is real work: the tilt e^{tB(I)}, the SAW-tree strong spatial mixing for the tilted bivariate model, the zero-freeness, the local CLT for the imbalance, and an algorithmic version of the local CLT. The proof of Proposition 2.10 (two-level contraction in arcsinh coordinates) is clean and self-contained. The hardness half imports the standard phase-coexistence gadget framework and shows the balance constraint exactly converts phase vectors into bisections. Theorem 1.1 on fixed slices is a nice complement, and it is honest about the leftover region (Problem 1.4).\n\nThe soft spot is where the stress-test says it is: Lemma 4.3. The pointwise terminal-law estimate (3), with the polynomial-factor bounds (6)–(8), is load-bearing for both hardness directions, and it is imported from [18,19] rather than reproved. The paper states the needed form explicitly and says the proof in [18,19] already transfers to the tree-augmented gadget; if that is accurate, the reduction goes through. A referee should check that the cited lemmas really give the pointwise ratio O(n^{-2θ}) for all terminal patterns, including exponentially rare ones, and not just total-variation closeness or a fixed number of terminals. If the transfer is wrong, Section 4.3's compatibility-factor calculation is unjustified. I do not have a counterexample, and the paper's own description suggests the transfer is sound; this is a verify-before-relying caveat, not a discovered error.\n\nLesser quibbles: several Fourier-analysis steps in Section 2.5 are said to be identical calculations to prior work; normal practice, but the local CLT is central enough that the paper would benefit from at least stating the lemmas it borrows. The FPTAS section says direct enumeration for n ≤ n0, which is fine.\n\nWho is this for: anyone working on approximate counting, phase coexistence, or global-constraint models. I would cite it and would bring it to reading group. It deserves peer review, preferably with a referee who knows the Sly gadget machinery.","headline":"Balanced hard-core threshold matches the unconstrained one; fixed-slice hardness is real. Main risk is imported Lemma 4.3, which deserves referee scrutiny.","tokens_in":56542,"tokens_out":2201,"would_cite":true,"duration_ms":28500,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","82B20","60F05","05C69","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that conditioning the hard-core model on bipartite graphs to use both sides equally leaves the computational threshold unchanged, while fixing exact slice densities creates a hard region.","keywords":["hard-core model","balanced independent sets","fixed slices","approximate counting","FPRAS","uniqueness threshold","phase coexistence","local CLT"],"falsifier":"Compute the phase-restricted partition functions Z_{G,+} and Z_{G,-} on the exact tree-augmented gadget for moderate n and λ>λ_c(Δ); if their ratio is not n^{O(1)} or the terminal laws deviate from i.i.d. Bernoulli with parameters q_±=α_±/(1−α_∓) by more than n^{-2θ}, Lemma 4.3 fails. On the algorithmic side, run the tilted rejection sampler on random bipartite graphs with λ<λ_c(Δ) and check whether the empirical acceptance probability Pr_{μ_{λ,t}}(B(I)=0) is actually Θ(n^{-1/2}) across the tilt window used.","tokens_in":55591,"feed_emoji":"⚖️","tokens_out":6023,"duration_ms":62929,"temperature":0.7,"pith_summary":"The paper studies two ways of constraining hard-core independent sets on bipartite graphs of maximum degree Δ: requiring equal occupation on the two sides, and fixing exact slice densities (αL, αR). It establishes a clean dichotomy for the balanced model: below the tree uniqueness threshold λ_c(Δ) there is an FPTAS and an efficient sampler, and above it there is neither unless NP=RP. This matches the known threshold for the unconstrained hard-core model on general bounded-degree graphs, meaning the balance constraint costs nothing at the level of computational phase transitions. For fixed slices, the paper proves a complementary hardness result: whenever the average density is between 1/Δ and 1/2 and the two side densities are more balanced than the phase-aligned ratios, approximate counting and sampling are NP-hard. The paper's significance is to map out which global constraints on bipartite independent sets are computationally benign and which are intrinsically hard.","feed_headline":"Balanced hard-core model keeps its exact threshold","feed_subtitle":"Tractable below the tree uniqueness threshold, NP-hard above it — the balance constraint changes nothing.","key_machinery":"The algorithmic machinery is the tilted hard-core model with partition function Z_G(λ;t)=Σ λ^{|I|} e^{t B(I)}, where B(I)=|I∩L|−|I∩R|, and the balance-conditioned law is the tilted law conditioned on B(I)=0. Strong spatial mixing on the self-avoiding walk tree is proved through a two-level contraction in the coordinate x↦arcsinh(√x), uniform over compact tilts; a zero-freeness region for the complex tilted partition function then yields a local central limit theorem for B(I), so the acceptance probability of rejection sampling is Ω(n^{-1/2}). The hardness machinery is a phase-coexistence gadget obtained from a random Δ-regular bipartite graph by deleting matching edges and attaching (Δ−1)-ar","core_discovery":"The paper's central claim, Theorem 1.2, is that for every fixed Δ≥3 and every fugacity λ, the balanced hard-core model on bipartite graphs with equal side sizes has exactly the same algorithmic threshold as the ordinary hard-core model on bounded-degree graphs: tractable (FPTAS + efficient sampler) when λ<λ_c(Δ)=(Δ−1)^{Δ−1}/(Δ−2)^Δ, and intractable (no FPRAS, no efficient sampler) when λ>λ_c(Δ), unless NP=RP. The tractable side is proved by a tilted hard-core model with left/right fugacities λe^t and λe^{-t}, whose balance variable has a near-Gaussian distribution with variance Θ(n), giving a rejection-sampling acceptance probability Ω(1/√n); the hard side is proved by a phase-coexistence ga","pith_inferences":["The boundary at the phase-aligned ratio may be a genuine computational phase transition: slices on the unbalanced side of that ratio might be tractable by an extension of the tilted-sampling argument, so one could test numerically whether fixed-slice sampling mixes rapidly exactly at the boundary.","The paper leaves λ=λ_c(Δ) open, conjecturing tractability via analogy with the unconstrained model; a numerical or rigorous check of whether the acceptance-probability bound persists at the critical fugacity would settle this gap.","The authors note that the phase-aligned-slice boundary in Theorem 1.1 may be an artifact of the proof rather than the true threshold; determining which slices are actually tractable would require new ideas and is a concrete next step.","The two-level contraction in arcsinh coordinates suggests the same tilting method could apply to other bipartite two-spin systems with a conserved difference, such as fixed-magnetization antiferromagnetic Ising models on bipartite graphs."],"forward_implications":["If λ<λ_c(Δ), balance is computationally free: the balanced partition function and distribution on bipartite graphs with |L|≈|R| admit an FPTAS and an efficient sampler.","If λ>λ_c(Δ), the balanced problem is as hard as MIN-BISECTION: a polynomial-time e^{N^ζ}-factor approximation for a small ζ would yield a randomized algorithm for MIN-BISECTION, so no FPRAS or efficient sampler exists unless NP=RP.","Fixed slices with average density in (1/Δ, 1/2) and side densities more balanced than the phase-aligned ratios are hard in the worst case, so slice-based decompositions cannot by themselves give worst-case algorithms for #BIS.","Phase-aligned slices (ratios equal to α_−(λ)/α_+(λ) or its reciprocal) are not ruled out by the hardness result, and their tractability is left as an explicit open problem."],"fun_headline_variants":["Balanced hard-core model shares exact threshold","Balance constraint doesn't change hard-core threshold","Hard-core threshold unchanged under balance condition","Balanced independent sets: same tractability line","No threshold shift from balancing hard-core model"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The hardness reductions rest on Lemma 4.3, imported without reproof, which asserts that in the non-uniqueness regime the random bipartite gadget has two well-separated phases with nearly independent terminal spins, partition functions within polynomial factors, and equal expected values; if these estimates fail for the exact tree-augmented gadget, the separation between balanced and unbalanced phase vectors collapses and the reductions to MIN-BISECTION and γ-MEBC break.","fun_headline_variants_meta":{"raw":{"variants":["Balanced hard-core model shares exact threshold","Balance constraint doesn't change hard-core threshold","Hard-core threshold unchanged under balance condition","Balanced independent sets: same tractability line","No threshold shift from balancing hard-core model"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"total_tokens":1397,"prompt_tokens":930,"completion_tokens":467,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":401}},"tokens_in":674,"tokens_out":467,"duration_ms":5331,"temperature":1.0,"reasoning_tokens":401,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T05:57:11.260216+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the phase-restricted partition functions Z_{G,+} and Z_{G,-} on the exact tree-augmented gadget for moderate n and λ>λ_c(Δ); if their ratio is not n^{O(1)} or the terminal laws deviate from i.i.d. Bernoulli with parameters q_±=α_±/(1−α_∓) by more than n^{-2θ}, Lemma 4.3 fails. On the algorithmic side, run the tilted rejection sampler on random bipartite graphs with λ<λ_c(Δ) and check whether the empirical acceptance probability Pr_{μ_{λ,t}}(B(I)=0) is actually Θ(n^{-1/2}) across the tilt window used.","supporting_citations":[],"review_version":1}