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.
Author: | Charilaos EfthymiouORCiDGND |
---|---|
URN: | urn:nbn:de:hebis:30:3-485070 |
Place of publication: | Frankfurt am Main |
Referee: | Amin Coja-OghlanORCiDGND, Alan Frieze |
Document Type: | Habilitation |
Language: | English |
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 |
HeBIS-PPN: | 439970792 |
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 | |
Sammlungen: | Universitätspublikationen |
Licence (German): | ![]() |