A new look at survey propagation and its generalizations

DOI10.1145/1255443.1255445zbMath1312.68175arXivcs/0409012OpenAlexW2621271919MaRDI QIDQ3546340

Elitza Maneva, Elchanan Mossel, Martin J. Wainwright

Publication date: 21 December 2008

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Proof of the satisfiability conjecture for large \(k\), Maximum independent sets on random regular graphs, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, On the Structure of Solution-Graphs for Boolean Formulas, Combinatorial statistics and the sciences, The asymptotic \(k\)-SAT threshold, Leveraging cluster backbones for improving MAP inference in statistical relational models, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting, The large deviations of the whitening process in random constraint satisfaction problems, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, Leveraging belief propagation, backtrack search, and statistics for model counting, Branching Process Approach for 2-Sat Thresholds, Unnamed Item, Satisfiability threshold for random regular \textsc{nae-sat}, On the survey-propagation equations in random constraint satisfiability problems, Pruning processes and a new characterization of convex geometries, Estimating satisfiability, The number of solutions for random regular NAE-SAT, Streamlining variational inference for constraint satisfaction problems, Biased landscapes for random constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion