Algorithmen und Dynamik unter Phasenübergangsphänomenen

• Antragsteller: Dr. Charilaos Efthymiou
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 265444125

• Erstellungsjahr: 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• (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
  (Siehe online unter https://doi.org/10.1137/17M1127144)
• 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
  (Siehe online unter https://doi.org/10.1137/140977643)
• 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
  (Siehe online unter https://doi.org/10.1137/17m1127144)
• Planting colorings silently. Combinatorics Probability and Computing (CPC), 26 (3), pp 338-366, 2017
  V. Bapst, A. Coja-Oghlan and C. Efthymiou
  (Siehe online unter https://doi.org/10.1017/S0963548316000390)
• 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
  (Siehe online unter https://doi.org/10.1007/s00220-018-3096-x)
• Local convergence of random graph colorings. In Combinatorica 38(2), pp 341-380, 2018
  A. Coja-Oghlan, C. Efthymiou and N. Jafaari
  (Siehe online unter https://doi.org/10.1007/s00493-016-3394-x)
• 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
  (Siehe online unter https://doi.org/10.1137/1.9781611975031.115)