TY  - THES
A1  - Ravelomanana, Jean Bernoulli
T1  - From replica symmetry to metastability in random constraint satisfaction problems language
N2  - This thesis concerns three specific constraint satisfaction problems: the k-SAT problem, random linear equations and the Potts model. We investigated a phenomenon called replica symmetry, its consequences and its limitation. For the $k$-SAT problem, we were able to show that replica symmetry holds up to a threshold $d^{*}$. However, after another critical threshold $d^{**}$, we discovered that replica symmetry could not hold anymore, which enabled us to establish the existence of a replica symmetry breaking region. For the random linear problem, a peculiar phenomenon occurs. We observed that a more robust version of replica symmetry (strong replica symmetry) holds up to a threshold $d=e$ and ceases to hold after. This phenomenon is linked to the fact that before the threshold $d=e$, the fraction of frozen variables, i.e. variable forced to take the same value in all solutions, is concentrated around a deterministic value but vacillates between two values with equal probability for $d>e$. Lastly, for the Potts model, we show that a phenomenon called metastability occurs. The latter phenomenon can be understood as a consequence of trivial replica symmetry breaking scheme. This metastability phenomenon further produces slow mixing results for two famous Markov chains, the Glauber and the Swendsen-Wang dynamics.
Y1  - 2022
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/69198
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-691980
N1  - Kumulative Dissertation – enthält die eingereichten Manuskriptversionen (Author Submitted Manuscripts) der folgenden Artikel: 

Coja-Oghlan, Amin; Müller, No͏e͏̈la; Ravelomanana, Jean B. (2020): Belief propagation on the random k-SAT model. math.PR, arXiv:2011.02303

Coja-Oghlan, Amin; Cooley, Oliver; Kang, Mihyun; Lee, Joon; Ravelomanana, Jean Bernoulli (2021): The sparse parity matrix. math.CO, arXiv:2107.06123v1

Cooley, Oliver; Lee, Joon; Ravelomanana, Jean B. (2021): Warning propagation: stability and subcriticality. math.CO, arXiv:2111.15577v1

Coja-Oghlan, Amin; Galanis, Andreas; Goldberg, Leslie Ann; Ravelomanana, Jean Bernoulli, Stefankovič, Daniel; Vigoda, Eric (2022): Metastability of the potts ferromagnet on random regular graphs. math.PR, arXiv:2202.05777v1
CY  - Frankfurt am Main
ER  -