Belief propagation guided decimation fails on random formulas

DOI10.1145/3005398zbMATH Open1426.68250OpenAlexW2573831607MaRDI QIDQ3177876FDOQ3177876

Authors: 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

Recommendations

• On belief propagation guided decimation for random \(k\)-SAT
• Analysing survey propagation guided decimationon random formulas
• The decimation process in random \(k\)-SAT
• The decimation process in random \(k\)-SAT
• Belief propagation on the random \(k\)-SAT model

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 (8)

• The decimation process in random \(k\)-SAT
• Counting Solutions to Random CNF Formulas
• The decimation process in random \(k\)-SAT
• Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
• On belief propagation guided decimation for random \(k\)-SAT
• The algorithmic hardness threshold for continuous random energy models
• Analysing survey propagation guided decimationon random formulas
• 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)