Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective

DOI10.1145/3313276.3316299zbMath1434.68338arXiv1808.07226OpenAlexW2964013189MaRDI QIDQ5212861

Frederic Koehler, Vishesh Jain, Andrej Risteski

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

variational methodsgraphical modelsmean-field approximationconvex hierarchiescorrelation rounding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation ⋮ Smoothed counting of 0–1 points in polyhedra ⋮ Lower tails via relative entropy ⋮ Fluctuations in mean-field Ising models ⋮ Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs ⋮ A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian ⋮ Learning polynomial transformations via generalized tensor decompositions ⋮ More on zeros and approximation of the Ising partition function

This page was built for publication: Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective