TY  - THES
A1  - Efthymiou, Charilaos
T1  - Phase transitions and dynamics for random constraint satisfaction problems
N2  - 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.
Y1  - 2018
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/48507
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-485070
CY  - Frankfurt am Main
ER  -