Algorithms and Dynamics under Phase Transition Phenomena

相变现象下的算法和动力学

• 批准号: 265444125
• 负责人: Dr. Charilaos Efthymiou
• 金额: --
• 依托单位: Schwerpunkt Diskrete Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2017-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/265444125?language=en
• 关键词: Algorithms; Dynamics; under; Phase; Transition

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.

该提案旨在推进一个基本的优化问题：随机约束满足问题（rCSP）。一些巧妙的，但数学上不严格的理论，从统计物理给研究的rCSP一个新的视角，所谓的腔方法作出了一些非常令人印象深刻的预测的最基本的性质rCSP。我们的目的是调查的合理性的一些最基本的预测的腔方法关于吉布斯分布的结构在各种rCSP模型。此外，我们打算研究一些最重要的本地算法的rCSP像消息传递算法，Glauber动力学，大都会过程，和一个新的算法最近建议的主要研究者这个项目。

项目成果

Sampling Random Colorings of Sparse Random Graphs

• DOI: 10.1137/1.9781611975031.115
• 发表时间: 2017-07
• 作者: Charilaos Efthymiou;Thomas P. Hayes;Daniel Stefankovic;Eric Vigoda

A Simple Algorithm for Sampling Colorings of G(n, d/n) Up to The Gibbs Uniqueness Threshold

一种对 G(n, d/n) 染色进行采样直至吉布斯唯一性阈值的简单算法

• DOI: 10.1137/140977643
• 发表时间: 2016
• 期刊: SIAM J. Comput.
• 作者: C. Efthymiou

Local Convergence of Random Graph Colorings

随机图着色的局部收敛

• DOI: 10.1007/s00493-016-3394-x
• 发表时间: 2018
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: A. Coja-Oghlan;C. Efthymiou;N. Jafaari
• 通讯作者: N. Jafaari

Planting Colourings Silently

默默地种植色彩

• DOI: 10.1017/s0963548316000390
• 发表时间: 2017
• 期刊: Combinatorics, Probability and Computing
• 作者: V. Bapst;A. Coja-Oghlan;C. Efthymiou
• 通讯作者: C. Efthymiou

Charting the Replica Symmetric Phase

绘制副本对称阶段图

• DOI: 10.1007/s00220-018-3096-x
• 发表时间: 2018
• 期刊: Communications in Mathematical Physics
• 影响因子: 2.4
• 作者: A. Coja-Oghlan;C. Efthymiou;N. Jaafari;M. Kang;T. Kapetanopoulos
• 通讯作者: T. Kapetanopoulos