On belief propagation guided decimation for random k-SAT

zbMath1373.68261arXiv1007.1328MaRDI QIDQ5365093

Amin Coja-Oghlan

Publication date: 29 September 2017

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

Mathematics Subject Classification ID

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

Related Items (6)

The algorithmic hardness threshold for continuous random energy models ⋮ Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem ⋮ Threshold saturation in spatially coupled constraint satisfaction problems ⋮ The Decimation Process in Random k-SAT ⋮ Minimal contagious sets in random regular graphs ⋮ Walksat Stalls Well Below Satisfiability

This page was built for publication: On belief propagation guided decimation for random k-SAT