Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models

zbMath1499.62192arXiv1901.07361MaRDI QIDQ4969061

Antonio Blanca, Eric Vigoda, Zongchen Chen, Daniel Štefanković, Ivona Bezáková

Publication date: 5 October 2020

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

zbMATH Keywords

Ising modelcoloringsgraphical modelsstructure learningdistribution testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypothesis testing in multivariate analysis (62H15) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probabilistic graphical models (62H22)

Related Items

Random-cluster dynamics on random regular graphs in tree uniqueness ⋮ Statistical limits of sparse mixture detection ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• The worm process for the Ising model is rapidly mixing
• Gibbs measures and phase transitions.
• Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture
• The complexity of approximating conservative counting CSPs
• An approximation trichotomy for Boolean \#CSP
• High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
• Some observations on the probabilistic algorithms and NP-hard problems
• Testing shape restrictions of discrete distributions
• The relative complexity of approximate counting problems
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
• An Efficient Learning Procedure for Deep Boltzmann Machines
• Efficiently Learning Ising Models on Arbitrary Graphs
• An Automatic Inequality Prover and Instance Optimal Identity Testing
• Polynomial-Time Approximation Algorithms for the Ising Model
• Property testing and its connection to learning and approximation
• The Complexity of Ferromagnetic Ising with Local Fields
• Expander graphs and their applications
• The Complexity of Distinguishing Markov Random Fields
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Random cluster dynamics for the Ising model is rapidly mixing
• Testing Ising Models
• Structure Learning of $H$-colorings
• Robust Characterizations of Polynomials with Applications to Program Testing
• Colouring graphs when the number of colours is nearly the maximum degree
• Approximating Pairwise Correlations in the Ising Model
• Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Statistical Mechanics of Lattice Systems
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• Approximating discrete probability distributions with dependence trees
• Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models