Dottorato in FISICA

Titolo della tesi: Exploiting atypicality in the Continuous Coloring Problem

In this thesis a relatively recent model, the continuous coloring, has been explored from the perspective of random constraint satisfaction problems. Its connection with the well known q-coloring problem of random graphs has been assessed; in particular, we have verified also the continuous problem to belong to the RFOT class for appropriate value of the parameters of the model. We study the model around its dynamic or clustering transition. A bias to the uniform measure over the solutions is introduced in order to postpone as much as possible the location of the dynamic transition, through what we call the complexity maximization procedure. This allows us to relate the properties of atypical solution found by local search procedures in an out-of-equilibrium setting to those of configurations that are typical in the biased measure. Our analysis suggests that out-of-equilibrium local algorithms can be attracted towards regions of the space of solutions clustering later than typical ones, i.e. at bigger connectivities. The atypicality of the found solutions is characterized in our setting in terms of the distribution of angular distances or gaps between nearest neighbours along the graph: smart algorithms are capable of spontaneously optimizing the gaps, satisfying the constraints in a more tight way, in order to beat the dynamic transition threshold.