Belief Propagation Guided Decimation Fails on Random Formulas

DOI10.1145/3005398zbMATH Open1426.68250OpenAlexW2573831607MaRDI QIDQ3177876FDOQ3177876

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

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

Cited In (3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177876)