Résumé IA · arXiv: 2610.40598v1 · cs.DS

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
Article original Soumis à arXiv le 29 Oct. 2026 98 pages Licence : NONEXCLUSIVE-DISTRIB 1.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

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.

Mots clés générés par l'IA : Modèle d’Ising antiferromagnétique fonction de partition graphes réguliers aléatoires seuil de Kesten–Stigum interpolation de Barvinok

Pour aller plus loin

  • Résumé Complet
  • Résumé vulgarisé
  • Article de blog
  • Abstract original
Cet article étudie l’approximation de la fonction de partition du modèle d’Ising antiferromagnétique sur un graphe régulier uniformément aléatoire de degré fixé \(d \geq 3\), lorsque le nombre de sommets \(n\) tend vers l’infini. Chaque configuration attribue un spin \(+1\) ou \(-1\) à chaque sommet, et son poids exponentiel favorise les arêtes reliant des spins opposés. La fonction de partition est la somme de ces poids sur l’ensemble des configurations. L’objectif est d’estimer cette fonction avec une précision multiplicative arbitrairement fine, plutôt que de déterminer uniquement la limite de son logarithme normalisé. La question centrale est de savoir si cette approximation reste réalisable en temps polynomial dans toute la phase dite « à symétrie des répliques ». Le seuil pertinent est celui de Kesten–Stigum, défini par \[ \beta_{\mathrm{KS}}=2\,\operatorname{arctanh}\!\left(\frac{1}{\sqrt{d-1}}\right). \] Pour les grands degrés, il est asymptotiquement équivalent à \(2/\sqrt{d-1}\). Il dépasse nettement le seuil d’unicité, qui régit les garanties sur les graphes arbitraires de degré maximal \(d\) et qui est d’ordre \(2/(d-1)\). Les auteurs proposent un algorithme déterministe couvrant les températures inverses positives qui restent à une distance relative constante du seuil de Kesten–Stigum. Plus précisément, pour tout \(\delta \in (0,1)\) fixé, l’algorithme s’applique à l’intervalle \([0,(1-\delta)\beta_{\mathrm{KS}}]\). Son temps de calcul est de la forme \((n/\varepsilon)^C\), où \(C\) dépend de \(d\) et de \(\delta\). Avec une probabilité tendant vers un lorsque \(n\) augmente, l’estimation obtenue est comprise entre \(e^{-\varepsilon}Z\) et \(e^\varepsilon Z\), où \(Z\) désigne la valeur exacte de la fonction de partition. Cette probabilité porte uniquement sur le choix du graphe aléatoire. Le principal résultat technique établit, avec cette même garantie asymptotique, l’absence de zéros de Fisher dans un voisinage complexe de largeur constante autour de l’intervalle considéré. Cette largeur dépend de \(d\) et de \(\delta\), mais pas de \(n\). Les auteurs en déduisent leur algorithme grâce à l’interpolation de Barvinok : après un changement de variable analytique, ils tronquent le développement de Taylor du logarithme de la fonction de partition à un degré d’ordre logarithmique en \(n/\varepsilon\). Le calcul efficace des coefficients repose sur le comptage de petits sous-graphes dans les graphes de degré borné. La démonstration de l’absence de zéros combine la formule de Jensen, des estimations de moments complexes et deux corrections essentielles. D’une part, une repondération analytique fondée sur les cycles courts neutralise les fluctuations multiplicatives persistantes de la fonction de partition. D’autre part, une troncature contrôle les rares graphes qui font diverger son second moment avant même le seuil de Kesten–Stigum. Le seuil du second moment non tronqué est donné par \[ \log\!\left(\frac{\sqrt d+1}{\sqrt d-1}\right). \] Une analyse restreinte aux configurations équilibrées et aux paires de faible recouvrement permet de dépasser cet obstacle. Des modèles plantés, une faible information gaussienne auxiliaire et la non-reconstruction sur les arbres fournissent des contrôles exponentiels des erreurs. Les moments complexes sont évalués au moyen d’intégrales de contour et de la méthode du col. Ce travail rapproche ainsi les transitions statistiques, analytiques et algorithmiques dans le cadre des graphes aléatoires. Il présente toutefois plusieurs limites : il ne traite pas le seuil critique lui-même, ne fournit pas directement d’algorithme d’échantillonnage et ne démontre pas le mélange rapide de la dynamique de Glauber jusqu’au seuil de Kesten–Stigum. En outre, la validité de l’approximation ne peut pas être certifiée efficacement pour un graphe donné. Enfin, l’optimalité supposée de ce seuil pour le calcul en temps polynomial demeure conjecturale.

Cette synthèse vous a-t-elle été utile ?

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Figures et graphiques

Posez une question sur une figure en indiquant son numéro ou en utilisant son bouton de question pour demander une analyse visuelle. Au maximum deux figures et quatre panneaux par question. Les valeurs lues sur les graphiques sont approximatives ; vérifiez les données originales.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 3 réécritures gratuites restantes aujourd'hui
Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Créer un compte gratuit Se connecter

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

Zotero
Alertes de citation Guide des alertes de citations
Lettre hebdomadaire Présenté dans « Informatique hors IA cette semaine » du 2 novembre 2026. Informatique hors IA cette semaine : des cartes à colorier aux machines à choisir

Les articles autour de celui-ci

Les voir sur une carte

Classé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

  1. Très proche Contexte plus large
    Computational thresholds for the fixed-magnetization Ising model
    Charles 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…

  2. Proche Autre approche du problème
    Approximation algorithms for the random-field Ising model
    Tyler 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…

  3. Proche Autre approche du problème
    Efficient Algorithms for Approximating Quantum Partition Functions
    Ryan 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.

  4. Proche Contexte plus large
    Sampling from the Potts model at low temperatures via Swendsen–Wang dynamics
    Antonio 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…

  5. Proche Contexte plus large
    On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
    Antonio 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…

  6. Proche Même question
    The complexity of approximating the complex-valued Ising model on bounded degree graphs
    Andreas 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…

  7. Proche Même méthode, autre problème
    Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
    Tyler 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…

  8. Proche Contexte plus large
    Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
    Hamidreza 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…

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.