Résumé IA · arXiv: 2610.40598v1 · cs.DS
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
L’essentiel
L’article établit un comptage approché polynomial pour l’Ising antiferromagnétique sur graphes réguliers aléatoires, à toute température inverse strictement inférieure au seuil de Kesten–Stigum.
Question
Peut-on approcher efficacement et avec une précision arbitraire la fonction de partition de l’Ising antiferromagnétique sur un graphe uniformément aléatoire d-régulier dans tout le régime sous le seuil de Kesten–Stigum ? Les auteurs étudient aussi l’absence de zéros complexes de cette fonction près de l’intervalle réel correspondant.
Méthode
Il s’agit d’une étude théorique sur des graphes d-réguliers à n sommets, avec d ≥ 3 fixé, analysés au moyen du modèle de configuration. La preuve combine formule de Jensen, estimations des premiers et seconds moments complexes, repondération fondée sur les cycles courts et troncature des contributions atypiques. L’algorithme déterministe utilise l’interpolation de Barvinok et une série de Taylor tronquée après O(log(n/ε)) termes ; son temps est (n/ε)^C, où C dépend de d et de la marge fixe au seuil.
Résultats
-
Résultat
Pour toute marge fixe δ entre 0 et 1 et toute température inverse comprise entre 0 et (1 − δ) fois le seuil de Kesten–Stigum, l’algorithme fournit une approximation multiplicative entre exp(−ε) et exp(ε), avec une probabilité tendant vers 1 sur le graphe aléatoire.
Voir le passage dans l’article
In this paper, we make progress on the high-temperature (small $\beta$) side of the aforementioned conjecture by giving the first polynomial-time approximate counting algorithm for all $\beta$ up to $\beta_{\mathsf{KS}}(d)$.
-
Résultat
Avec une probabilité tendant vers 1, la fonction de partition ne possède aucun zéro dans un voisinage complexe de largeur constante de l’intervalle allant de 0 à (1 − δ) fois le seuil de Kesten–Stigum.
Voir le passage dans l’article
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.
-
Résultat
La repondération permet de faire coïncider asymptotiquement la contribution quasi orthogonale au second moment avec le carré du premier moment.
Voir le passage dans l’article
Property Item (R3) says that reweighting makes the near-orthogonal contribution to the second moment match the first moment squared.
Limites
- Les garanties portent sur une marge fixe strictement sous le seuil et ne couvrent pas le seuil lui-même.
- Le comptage approché obtenu ne fournit pas immédiatement un algorithme d’échantillonnage approché de la mesure de Gibbs.
Voir le passage dans l’article
Our approximate counting algorithm does not immediately imply an approximate sampling algorithm for the Gibbs measure $\mu_{G,\beta}$.
- Les auteurs ne savent pas certifier efficacement, pour un graphe donné, que les conditions garantissant la correction de l’algorithme sont satisfaites.
Voir le passage dans l’article
Unfortunately, we do not know how to show that our algorithm is certifiable in this sense.
Portée
Selon les auteurs, ce résultat porte pour la première fois le comptage approché polynomial jusqu’à toute valeur strictement sous le seuil de Kesten–Stigum, au-delà des plages précédemment accessibles. Il étaye la conjecture reliant, en cas moyen, la transition de complexité algorithmique et l’accumulation des zéros de la fonction de partition, sans établir l’optimalité de ce seuil.
Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.
Posez des questions sur cet article à notre assistant IA
Comment discuter avec cet article ? Guide illustré
Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.
Gardez cette conversation — un compte gratuit conserve vos questions et réponses, vos collections d’articles et vos alertes.
Créer un compte gratuitOutils pour cet article
Outils avancés Premium
Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium
Les articles autour de celui-ci
Les voir sur une carteClassés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
Computational thresholds for the fixed-magnetization Ising modelCharles Carlson, Ewan Davies, Alexandra Kolla et al. · 2021 · Symposium on the Theory of Computing · cité 14 fois · Pas encore résumé
Computational thresholds for the modèle ferromagnétique à magnétisation fixée étudie la difficulté du comptage et de l’échantillonnage, plutôt que l’approximation sur graphes aléatoires d-réguliers.
Résumé scientifique
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of +1 and −1 spins). In…
-
Approximation algorithms for the random-field Ising modelTyler Helmuth, Holden Lee, Will Perkins et al. · 2021 · SIAM Journal on Discrete Mathematics · cité 3 fois · Pas encore résumé
Approximation algorithms for the random-field Ising model construit des schémas d’approximation et d’échantillonnage pour Ising ferromagnétique sous des champs gaussiens aléatoires.
Résumé scientifique
Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exists. This motivates an average-case question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree $\Delta$. We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are IID Gaussians with variance larger than a constant dependi…
-
Efficient Algorithms for Approximating Quantum Partition FunctionsRyan L. Mann, Tyler Helmuth · 2020 · Journal of Mathematics and Physics · cité 30 fois · Pas encore résumé
Efficient Algorithms for Approximating Quantum Partition Functions approche les fonctions de partition par développement en amas à haute température, pour des modèles quantiques.
Résumé scientifique
We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netocny and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.
-
Sampling from the Potts model at low temperatures via Swendsen–Wang dynamicsAntonio Blanca, Reza Gheissari · 2023 · IEEE Annual Symposium on Foundations of Computer Science · cité 7 fois · Pas encore résumé
Sampling from the Potts model at low temperatures via Swendsen–Wang dynamics étudie l’échantillonnage du Potts ferromagnétique à basse température sur des graphes structurés.
Résumé scientifique
Sampling from the q-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem is computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the q-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of the widely-used Swen…
-
On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamicsAntonio Blanca, Reza Gheissari · 2023 · Probability theory and related fields · cité 5 fois · Pas encore résumé
On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics examine l’échantillonnage du Potts à basse température par une dynamique de amas aléatoires.
Résumé scientifique
Sampling from the q-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem may be computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the q-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of random-cluster d…
-
The complexity of approximating the complex-valued Ising model on bounded degree graphsAndreas Galanis, L. Goldberg, Andrés Herrera-Poyatos · 2021 · SIAM Journal on Discrete Mathematics · cité 10 fois · Pas encore résumé
The complexity of approximating the complex-valued Ising model on bounded degree graphs analyse la complexité d’approximation de la fonction de partition d’Ising pour des interactions complexes.
Résumé scientifique
We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractab…
-
Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphsTyler Helmuth, Matthew Jenssen, Will Perkins · 2020 · Annales De L Institut Henri Poincare-probabilites Et Statistiques · cité 34 fois · Pas encore résumé
Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs utilise modèles polymères et développement en amas pour compter et échantillonner sur graphes réguliers aléatoires.
Résumé scientifique
For $\Delta \ge 5$ and $q$ large as a function of $\Delta$, we give a detailed picture of the phase transition of the random cluster model on random $\Delta$-regular graphs. In particular, we determine the limiting distribution of the weights of the ordered and disordered phases at criticality and prove exponential decay of correlations away from criticality. Our techniques are based on using polymer models and the cluster expansion to control deviations from the ordered and disordered ground states. These techniques also yield efficient approximate counting and sampling algorithms for the Potts and random cluster models on random $\Delta$-regular graphs at all temperatures when $q$ is large…
-
Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- AlgorithmsHamidreza Behjoo, M. Chertkov · 2023 · Trans. Mach. Learn. Res. · cité 1 fois · Pas encore résumé
Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms propose une approximation variationnelle de la fonction de partition d’Ising.
Résumé scientifique
Computing the partition function, $Z$, of an Ising model over a graph of $N$ \enquote{spins} is most likely exponential in $N$. Efficient variational methods, such as Belief Propagation (BP) and Tree Re-Weighted (TRW) algorithms, compute $Z$ approximately by minimizing the respective (BP- or TRW-) free energy. We generalize the variational scheme by building a $\lambda$-fractional interpolation, $Z^{(\lambda)}$, where $\lambda=0$ and $\lambda=1$ correspond to TRW- and BP-approximations, respectively. This fractional scheme -- coined Fractional Belief Propagation (FBP) -- guarantees that in the attractive (ferromagnetic) case $Z^{(TRW)} \geq Z^{(\lambda)} \geq Z^{(BP)}$, and there exists a un…
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 2 novembre 2026.
Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.