On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
AI 速览：作者提出首个在均匀随机 d-正则图上、对反铁磁 Ising 模型在直至 Kesten-Stigum 阈值的全部逆温度范围内以任意高精度估计配分函数的多项式时间算法。
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.
Classical communication over quantum channels: does entanglement help in nature?
Peixue Wu
AI 速览：作者提出Schur加权块熵不等式，证明所有相位协变信道（含多能级振幅阻尼、广义退相位、阻尼-退相位信道）在经典通信中不存在纠缠优势。
Can entangling codewords across independent uses of a quantum channel improve the rate of classical communication? An old conjecture states that there is no such entanglement advantage for all channels. Although Hastings's result and follow-up works disproved this conjecture, it turns out that enormous dimension is required to construct a channel where entanglement enhances classical communication. This indicates that there might be no entanglement advantage for many physical channels, or for all low dimensional channels. Motivated by recent progress on (generalized) amplitude damping channels, we propose a general Schur-weighted block entropy inequality, and show that there is no entanglement advantage for all phase-covariant channels including multi-level amplitude damping channels, generalized dephasing channels, and damping-dephasing channels. As a by-product, we also recover the recently established result that there is no entanglement advantage for all qubit channels.
Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold
Zejia Chen, Chunyang Wang, Xinyuan Zhang
AI 速览：作者在随机 d-正则图上证明硬核模型与反铁磁 Potts 模型（含正常 q-染色）在副本对称区内具有零点自由区域，并由此得到多项式时间近似配分函数的算法。
We study antiferromagnetic spin systems on random regular graphs through the lens of the phase transitions characterized by the complex zeros of the partition function. Our motivating examples include the hardcore model and the antiferromagnetic Potts model (including proper $q$-colorings at $β=0$). For both models on random $d$-regular graphs, we establish, with high probability over the graph, zero-free regions throughout the interior of the replica-symmetric regime. Asymptotically, this regime extends up to tree occupation density $$α< α_{\mathrm{RSB}}(d) = (2\log d - 2\log\log d + 2 - 2\log 2 + o_d(1))/d$$ for the hardcore model and up to degree $$d < d_{\mathrm{RSB}}(q) = (2q-1)\log q - 2\log 2 + o_q(1)$$ for proper $q$-colorings. Leveraging the standard algorithmic implications of zero-freeness, we obtain deterministic polynomial-time algorithms that multiplicatively approximate the corresponding partition functions at fixed rational parameters throughout this regime, with high probability over the graph. Our algorithmic guarantees significantly improve upon prior work and extend beyond the parameter ranges reached by previously known search algorithms. To establish our results, we first develop reinforced small subgraph conditioning, which resolves short-cycle fluctuations in the complex plane by lifting classical small subgraph conditioning on random regular graphs to random holomorphic functions. Second, we overcome the standard second-moment barrier caused by the exponential blowup of the bare second moment inside the replica-symmetric phase, by showing that replica symmetry implies a nonpositive Bethe functional and upgrading planted overlap concentration to an exponentially small bound, which enables a typical-graph truncation that controls complex second moments up to the replica symmetry breaking threshold.
AI 速览：作者提出用状态判别方法研究无辅助噪声量子信道通信，并基于Petz恢复映射构造纠缠生成码与误差界。
We develop a state discrimination approach to unassisted quantum communication through a noisy quantum channel. Starting from the operational duality between entanglement recovery and state discrimination, we construct entanglement-generation codes with explicit decoders constructed from Petz recovery maps. The resulting error bounds hold for every number of channel uses and are expressed in terms of Petz-Rényi coherent information. For product sources, they yield exponential error decay at rates below coherent information.
While universal approximation theorems theoretically underpin the representation capabilities of machine learning models, they have two shortcomings: They do not focus on efficient representations and they tend to be insensitive to depth and other heuristically important properties. In this work we show that these two shortcomings are intertwined. We prove that machine learning models which are deeper or have higher-order interactions can efficiently represent a larger set of functions, i.e. have larger efficient reach. It follows that deep Boltzmann machines (DBMs) have maximal efficient reach, restricted Boltzmann machines (RBMs) sub-maximal, and k-body generalizations of RBMs form a hierarchy between the two, even though all are universal. More generally, (i) we provide a full characterization of machine learning models with maximal efficient reach; (ii) we derive separations between deep and shallow models for three representation tasks; and (iii) we prove that the efficient reach of shallow models constitutes an infinite hierarchy indexed by the interaction order. The proofs draw on different methodologies, namely on (i) a recent characterization of universal spin models; (ii) computational complexity bounds for spin models; and (iii) communication complexity bounds applied to shallow models. This work shows that universal machine learning models can strongly differ in their efficient representation capabilities, and provides a theoretical foundation for heuristic observations.
Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph $H$, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on $H$, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of $H$. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of $\left( H_n \right)_{n \in \mathbb{N}}$ converges locally in probability to a rooted graph $H^*$, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of $H^*$. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.
Hybrid domain decomposition methods provide a flexible framework for coupling full order models (FOMs) and reduced order models (ROMs), but typically assume the model assigned to each subdomain is fixed throughout a simulation. This is limiting for transient problems in which localized features propagate through the domain and the regions requiring high-fidelity resolution change over time. We introduce a reinforcement learning (RL)-based approach for online adaptation of FOM-ROM models coupled via the overlapping Schwarz alternating method (O-SAM), an iterative domain decomposition method that solves subdomain-local problems while exchanging solution information through transmission boundary conditions on overlapping interfaces. Deep Q-networks (DQNs) are trained offline to select among subdomain-local FOMs and pre-trained Operator Inference (OpInf) ROMs using a reward balancing accuracy, cost, and model-switching frequency. Once trained, the policies are deployed predictively on problem instances not seen during training, without requiring a reference FOM solution. We demonstrate the approach on two examples: a 1D advection-diffusion problem with a moving front, and a 3D linear elastic wave propagation problem implemented in the Norma.jl solid mechanics code. For the advection-diffusion benchmark, the learned policy dynamically allocates high-fidelity resolution as the front propagates and outperforms static FOM/ROM assignments; letting the agent also adapt the domain decomposition provides no further benefit. For the elastic wave benchmark, learned policies for two and three subdomain decompositions track the propagating wave by assigning FOMs to subdomains containing the wave and ROMs elsewhere, as expected. Our results demonstrate the potential of RL to enable predictive online adaptation of model fidelity within Schwarz-based hybrid simulations.
Computationally expensive simulations and real-world observations often provide data at a lower temporal resolution than downstream tasks require. Averaging observations at fixed grid points can introduce errors, and motion estimates alone do not determine how the physical field values change. In this work, we study whether learning to correct a simple numerical interpolation improves the reconstruction of intermediate scientific fields. Our model, interpolative FLow EXpert (iFLEX), first estimates the missing field by taking a weighted average of the two observations at each grid point, giving more weight to the observation closer to the requested time. During training, subtracting this estimate from an observed intermediate field gives the residual that a conditional diffusion model learns to generate. Both observations condition the model, together with the target time, the interval between observations, and available physical parameters. To reconstruct an unobserved intermediate field, the generated residual is added to the weighted average. We evaluate iFLEX on Navier-Stokes Kraichnan turbulence, Shanghai radar precipitation, and sea surface temperature. Across these datasets, iFLEX achieves lower reconstruction error than the evaluated baselines, including optical-flow and diffusion models developed for video frame interpolation in computer vision. In a controlled turbulence comparison at a Reynolds number of 36,000, learning the residual reduces relative Frobenius norm error from about 13.7 for direct field generation to 10.5, with the diffusion backbone and training setup held fixed. Code is available at https://github.com/paulpuren/iflex.
Priyanka Grover, Hemant K. Mishra, Sarishti Singh, Temjensangba
The symplectic interlacing theorem states that the symplectic spectrum of a $2n \times 2n$ real symmetric positive definite matrix satisfies a $2k$-step interlacing relation with the symplectic spectrum of every $2(n-k) \times 2(n-k)$ $s$-principal submatrix. We prove the converse in this paper. More precisely, given a positive global symplectic spectrum of size $n$ and a positive local symplectic spectrum of size $n-k$ satisfying the $2k$-step interlacing inequalities, we construct a $2n \times 2n$ real symmetric positive definite matrix having the prescribed global symplectic spectrum and a $2(n-k) \times 2(n-k)$ $s$-principal submatrix of it having the prescribed local symplectic spectrum. Our main tool is a reduction of $s$-principal compression to a rank-$k$ singular value perturbation. In the context of the Gaussian quantum marginal problem, our result implies that the symplectic interlacing inequalities are not merely necessary conditions on Gaussian marginals, but are also the complete spectral compatibility conditions for the global-versus-local-mode marginal problem.