Belief propagation guided decimation fails on random formulas

DOI10.1145/3005398MaRDI QIDQ3177876zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(9)

• The decimation process in random \(k\)-SAT
• Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
• Analysing survey propagation guided decimationon random formulas
• The algorithmic hardness threshold for continuous random energy models
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• The decimation process in random \(k\)-SAT
• On belief propagation guided decimation for random \(k\)-SAT
• Belief propagation on the random \(k\)-SAT model
• Counting solutions to random CNF formulas

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)