@inbook{60ac9c4166d64aed810bca78836335e3,
title = "Chapter 22: Connections to statistical physics",
abstract = "This chapter surveys a part of the intense research activity that has been devoted by theoretical physicists to the study of randomly generated k-SAT instances. It can be at first sight surprising that there is a connection between physics and computer science. However lowerature statistical mechanics concerns precisely the behaviour of the low-lying configurations of an energy landscape, in other words the optimization of a cost function. Moreover the ensemble of random k-SAT instances exhibit phase transitions, a phenomenon mostly studied in physics (think for instance at the transition between liquid and gaseous water). Besides the introduction of general concepts of statistical mechanics and their translations in computer science language, the chapter presents results on the location of the satisfiability transition, the detailed picture of the satisfiable regime and the various phase transitions it undergoes, and algorithmic issues for random k-SAT instances.",
author = "Fabrizio Altarelli and R{\'e}mi Monasson and Guilhem Semerjian and Francesco Zamponi",
note = "Publisher Copyright: {\textcopyright} 2021 The authors and IOS Press. All rights reserved.",
year = "2021",
month = jan,
day = "1",
doi = "10.3233/FAIA201006",
language = "English",
series = "Frontiers in Artificial Intelligence and Applications",
publisher = "IOS Press BV",
pages = "859--901",
editor = "Armin Biere and Marijn Heule and \{Van Maaren\}, Hans and Toby Walsh",
booktitle = "Handbook of Satisfiability",
}