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

• Final Report Year: 2019

Final Report Abstract

The main objective of the project is to study natural algorithmic problems that arise in the context of random Constraint Satisfaction Problems (r-CSP). Particularly, our focus is on sampling problems. The study of such problems have been given a new perspective from physicists who, recently, introduced the ingenuous alas mathematically non-rigorous Cavity Method. In the course of the project, we studied certain dynamical processes, “dynamics” for sampling, with particular focus on analysing the mixing properties of Glauber dynamics. Furthermore, we used ideas emanating from statistical physics to develop new sampling algorithm. Also, we put a lot of effort to put certain parts of the Cavity Method on a (mathematically) rigorous basis. During the project we realized that our study is also related to questions emanating from data science and more specifically from community detection. Mainly, this is due to the fact that basic notions from the Cavity Method emerge naturally in the study of inference problems in community detection. Some of our latest papers include results related to community detection, too. Furthermore, the ideas we use for understanding our algorithm are fundamental ones. It is not a surprise that we use them to analyze sampling algorithms like Glauber dynamics and Belief propagation for worst case graph instances.

Publications

• (2019) Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. SIAM J. Comput. (SIAM Journal on Computing) 48 (2) 581–643
  Efthymiou, Charilaos; Hayes, Thomas P.; Štefankovič, Daniel; Vigoda, Eric; Yin, Yitong
  
• A simple algorithm for sampling colourings of G(n, d/n) up to Uniqueness threshold. In SIAM Journal on Computing (SICOMP), 45 (6), pp 2087-2116, 2016
  C. Efthymiou
  
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. In the proc.of 57th Symposium on Foundations of Computer Science (FOCS’16), pp 704-713, 2016
  C. Efthymiou, T. Hayes, D. Stefankovic, E.Vigoda and Y. Yin
  
• Planting colorings silently. Combinatorics Probability and Computing (CPC), 26 (3), pp 338-366, 2017
  V. Bapst, A. Coja-Oghlan and C. Efthymiou
  
• Charting the Replica Symmetry Phase. In Communications in Mathematical Physics (CIMP) 359(2), pp 603-698, 2018
  A. Coja-Oghlan, C. Efthymiou, N. Jaafari, M. Kang and T. Kapetanopoulos
  
• Local convergence of random graph colorings. In Combinatorica 38(2), pp 341-380, 2018
  A. Coja-Oghlan, C. Efthymiou and N. Jafaari
  
• Sampling Random Colorings of Sparse Random Graphs. In the proc. of 29th Symposium on Discrete Algorithms (SODA’18), pp 1759 - 1771, 2018
  C. Efthymiou, T. Hayes, D. Stefankovic and E.Vigoda