statistical physics modelers

Abstract: We give the first polynomial-time algorithm to estimate the partition function of the antiferromagnetic Ising model on the uniformly random $d$-regular graph to arbitrarily high accuracy for all inverse temperatures up to the Kesten-Stigum threshold. This is the entire regime in which the model is "replica symmetric," and is conjectured to be optimal for polynomial-time counting and sampling. To achieve our algorithmic result, we establish the absence of Fisher zeros for the partition function in a constant-width strip around the interval from $0$ up to the Kesten-Stigum threshold, with high probability over the randomness of the input graph. AI Disclosure: The overarching vision and proof architecture were developed solely by the authors without AI input. GPT 5.5 Pro was used, with extensive guidance from the authors, for only a few minor technical aspects of the proof. The authors independently verified correctness and wrote everything by hand. We take full responsibility for its contents. A more detailed statement can be found in Section 1.2.

Abstract: We study a jump-modified Wasserstein gradient flow of the squared maximum mean discrepancy generated by the energy kernels $K(z)=-|z|^q$, $0<q<2$, in every dimension $d\ge2$ as well as the one-dimensional range $1\le q<2$. Under subcritical density and finite-moment assumptions, we prove global well-posedness. The added jumps transfer mass toward smaller values of the first variation and dissipate the same MMD energy as the transport term. Under our hypotheses on the target and jump rates, every Borel probability measure with finite MMD energy and zero jump dissipation is equal to the target. Combining this rigidity with compactness and a second-moment identity yields convergence to the target from finite-second-moment data, without additional uniform-in-time density or moment assumptions. We also construct a global collision-free particle process whose energy is nonincreasing along each path. A quantitative mean-field estimate applies to general initial empirical approximations, including deterministic configurations; propagation of chaos for exchangeable data and long-time target approximation follow as consequences.

Abstract: LABS are a fundamental combinatorial optimization problem arising in sequence design and statistical physics, yet the formal complexity of the standard fixed-geometry problem remains unresolved. We study how zero-energy complexity changes when support geometry is included as part of the input and then progressively restricted. For unary standard LABS, we establish membership in $\NP$ and a sparsity/Mahaney consequence: Karp NP-hardness would imply $\Ptime=\NP$. For Pair-Set-LABS and Masked-LABS, zero-energy feasibility is polynomial-time decidable when every pair group or masked row has at most three terms and is NP-complete when four terms are allowed. NP-completeness persists when active supports are restricted to contiguous intervals.

Abstract: We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.

Abstract: We study general maximal hard-core models on periodic lattice-type graphs. While for standard models, phase coexistence may arise for high activity, for maximal models this behavior may occur also for sufficiently low activity values. Relying on the concept of volume allocation, we develop a {\em unified set of assumptions} that imply the Peierls condition, a convergent cluster expansion for the partition function, and hence the conclusions of Pirogov-Sinai theory for this class of models. We further check these assumptions for a number of examples including standard lattice-type periodic graphs, proving crystallization for both high and low activity. We also derive estimates for the values of activity that bound the phase coexistence regions in the phase diagram, rewriting for this purpose the proof of a technical result in the derivation of Pirogov-Sinai theory.

Abstract: We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.

Abstract: We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion for tractability. We also characterize exactly which fixed positive vertex weights preserve tractability, with both classifications extending from algebraic weights to fixed real weights in a prescribed exact representation. Our proof hinges on an entropy-based continuation argument: maximal logarithmic support identifies distance kernels as maximum-entropy completions, extending their positive definiteness throughout the parameter interval. This enables distance geometry to recover hidden product coordinates even when planar gadgets cannot distinguish colors; counting-hardness arguments then force the factors to be zero-field Boolean Ising interactions. The classification also yields complete tractability criteria for clock models, coupled Ising systems, and planar contractions of stoquastic imaginary-time kernels. All results have been formally verified in Lean 4.

Abstract: Inference-time scaling adapts pretrained diffusion models to new sampling tasks without additional training. Existing methods rely primarily on Monte Carlo sampling with more particles, yet are premised on the pretrained model being exact. In practice, data and training limitations make the model imperfect, and these methods inherit its error. More particles reduce Monte Carlo error but cannot remove the mismatch between the endpoint and the desired target or the error in tracking the prescribed probability path. We introduce the Energy-based Feynman-Kac Corrector (EBFKC), a framework for energy-based diffusion models that corrects these errors on the fly given a reference energy. We first derive Feynman-Kac dynamics that track a prescribed path exactly in the continuous-time population limit even when the model is imperfect, and approximate these dynamics using sequential Monte Carlo with variance-controlling guidance. To remove the endpoint mismatch, we use the pretrained energy as a surrogate along the diffusion path and progressively incorporate the discrepancy between the learned and target terminal energies. Experiments on Gaussian mixture models, particle systems, alanine dipeptide, and alanine tetrapeptide show that our method closely matches target distributions and molecular free-energy profiles under annealing and reward tilting, whereas standard inference-time scaling baselines retain substantial sampling errors.

Abstract: Isoperimetric inequalities on the Boolean hypercube play a fundamental role in the analysis of Boolean functions. These inequalities have been established primarily for the uniform measure and for biased product measures, often through Fourier-analytic or inductive arguments. We develop a curvature-based semigroup framework to establish isoperimetric inequalities for measures with weakly dependent coordinates. In particular, we show that a Dobrushin-type condition, together with marginal boundedness of the distribution, implies the local Bobkov inequality, Talagrand's $L^1$--$L^2$ and variance--surface-area inequalities, the Kahn--Kalai--Linial inequality, and the Eldan--Gross inequality. Our results apply to zero-field Ising models with interaction matrix $J$ throughout the Dobrushin uniqueness regime $\|J\|_1<1$. The framework builds on discrete Bakry--Émery theory and gradient estimates and can also be extended to measures on Hamming slices or hypergrids.

Abstract: For every fixed $0<\varepsilon\le1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in\mathbb{R}_{\ge0}^{n\times n}$, returns $Q$ satisfying $\operatorname{per} A\le Q\le(1+\varepsilon)^n\operatorname{per} A$.