Phase transitions and dynamics for random constraint satisfaction problems

  • The thesis is about random Constraint Satisfaction Problems (rCSP). These are random instances of classical problems in NP. In the literature the study of rCSP involve identifying-locating phase transition phenomena as well as investigating algorithmic questions. Recently, some ingenious however mathematically non-rigorous theories from statistical physics have given the study of rCSP a new perspective; the so-called Cavity Method makes some very impressing predictions about the most fundamental properties of rCSP. In this thesis, we investigate the soundness of some of the most basic predictions of the Cavity Method, mainly, regarding the structure of the so-called Gibbs distribution on various rCSP models. Furthermore, we study some fundamental algorithmic problem related to rCSP. This includes both analysing well-known dynamical process (dynamics) like Glauber Dynamics, Metropolis Process, as well as proposing new algorithmic approaches to some natural problems related to rCSP.

Download full text files

Export metadata

Author:Charilaos EfthymiouORCiDGND
Place of publication:Frankfurt am Main
Referee:Amin Coja-OghlanORCiDGND, Alan Frieze
Document Type:Habilitation
Date of Publication (online):2018/11/12
Year of first Publication:2018
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Granting Institution:Johann Wolfgang Goethe-Universität
Date of final exam:2018/12/03
Release Date:2018/12/13
Page Number:525
Institutes:Informatik und Mathematik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht