Belief Propagation Guided Decimation Fails on Random Formulas

DOI10.1145/3005398zbMath1426.68250OpenAlexW2573831607MaRDI QIDQ3177876

Amin Coja-Oghlan

Publication date: 2 August 2018

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

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

zbMATH Keywords

satisfiabilityrandom structuresbelief propagation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

The algorithmic hardness threshold for continuous random energy models ⋮ Counting Solutions to Random CNF Formulas ⋮ Belief propagation on the random \(k\)-SAT model

This page was built for publication: Belief Propagation Guided Decimation Fails on Random Formulas