Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models

DOI10.1145/3268930zbMath1427.68128OpenAlexW2938658492WikidataQ124988727 ScholiaQ124988727MaRDI QIDQ5244383

Ankur Moitra

Publication date: 21 November 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3268930

zbMATH Keywords

graphical modelsapproximate countingLovász local lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (6)

Counting Solutions to Random CNF Formulas ⋮ New bounds for the Moser‐Tardos distribution ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Dynamic Sampling from Graphical Models ⋮ Implementations and the independent set polynomial below the Shearer threshold

This page was built for publication: Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models