The Decimation Process in Random $k$-SAT

DOI10.1137/110842867zbMath1263.68119arXiv1102.3145OpenAlexW3105349673MaRDI QIDQ4915183

Amin Coja-Oghlan, Angélica Yohana Pachón Pinzón

Publication date: 9 April 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionsrandom structuresbelief propagation\(k\)-SAT

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Planting Colourings Silently ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Unnamed Item ⋮ Biased landscapes for random constraint satisfaction problems

This page was built for publication: The Decimation Process in Random $k$-SAT