Algorithms and Dynamics under Phase Transition Phenomena

• Applicant: Dr. Charilaos Efthymiou
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 265444125

The proposal aims at making advances in a fundamental optimisation problem: random Constraint Satisfaction Problems (rCSP). 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.Our aim is to investigate the soundness of some of the most basic predictions of the Cavity Method regarding the structure of the Gibbs distribution on various rCSP models. Further, we intend to study some of the most important local algorithms for rCSP like Message Passing Algorithms, Glauber Dynamics, Metropolis process, and a new algorithm suggested recently by the Prime Investigator of this project.

• DFG Programme: Research Grants