The Decimation Process in Random k-SAT
From MaRDI portal
Publication:3012815
DOI10.1007/978-3-642-22006-7_26zbMath1332.68069MaRDI QIDQ3012815
Amin Coja-Oghlan, Angélica Yohana Pachón Pinzón
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_26
68Q25: Analysis of algorithms and problem complexity
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Cites Work
- Pairs of SAT-assignments in random Boolean formulæ
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Random Formulas Have Frozen Variables
- Survey propagation: An algorithm for satisfiability
- On belief propagation guided decimation for random k-SAT
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Threshold values of random K‐SAT from the cavity method
- On the solution‐space geometry of random constraint satisfaction problems