Alessandro Zorzan
Disorder Chaos in Diluted Spin Glass models and Constraint Satisfaction Problems.
Rel. Andrea Pagnani. Politecnico di Torino, Master of science program in Physics Of Complex Systems, 2025
|
Preview |
PDF (Tesi_di_laurea)
- Thesis
Licence: Creative Commons Attribution Non-commercial No Derivatives. Download (893kB) | Preview |
Abstract
This thesis investigates the phenomenon of disorder chaos in disordered systems, with a particular focus on random constraint satisfaction problems (CSPs) such as random k-SAT. We begin by introducing the framework of spin glass models, reviewing the Sherrington–Kirkpatrick (SK) model and its generalization to mixed p-spin models. In these fully connected systems, the presence of disorder chaos is well understood and has been rigorously established by Chen and Panchenko: even small perturbations of the disorder cause typical equilibrium configurations to become asymptotically orthogonal, confirming earlier predictions by Bray and Moore. We then turn to diluted models, where each variable participates only in a finite number of constraints.
We consider k-SAT and related problems (NAESAT, XORSAT, hypergraph 2-coloring), we reinterpret them as Hamiltonians with random interactions, highlighting the analogy with spin glass systems
Relators
Academic year
Publication type
Number of Pages
Course of studies
Classe di laurea
Aziende collaboratrici
URI
![]() |
Modify record (reserved for operators) |
