Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region

DOI10.1145/2785964zbMath1426.68304arXiv1305.2902OpenAlexW2295121732MaRDI QIDQ3177756

Daniel Štefanković, Andreas Galanis, Eric Vigoda

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.2902

zbMATH Keywords

phase transitionsrandom regular graphsPotts modelcoloringsinapproximabilityapproximate counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Dynamic and nonequilibrium phase transitions (general) in statistical mechanics (82C26) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (28)

\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs ⋮ Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree ⋮ Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ What can be sampled locally? ⋮ Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \) ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ Unnamed Item ⋮ Counting Constraint Satisfaction Problems. ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ Charting the replica symmetric phase ⋮ Uniqueness for the 3-state antiferromagnetic Potts model on the tree ⋮ The satisfiability threshold for random linear equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ Random-cluster dynamics on random regular graphs in tree uniqueness ⋮ Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ The Cut Metric for Probability Distributions ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ A reverse Sidorenko inequality ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Dynamic Sampling from Graphical Models ⋮ Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region