Alessandro Zorzan
Disorder Chaos in Diluted Spin Glass models and Constraint Satisfaction Problems.
Rel. Andrea Pagnani. Politecnico di Torino, Corso di laurea magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi), 2025
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: 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
Relatori
Anno Accademico
Tipo di pubblicazione
Numero di pagine
Corso di laurea
Classe di laurea
Aziende collaboratrici
URI
![]() |
Modifica (riservato agli operatori) |
