学术报告（丁剑 9.22）

Abstract:

In this talk, I will describe how algorithms and complexity theory, probability and statistical physics, as well as theoretical statistics interact with each other on the topic of random combinatorial optimization problems. In particular, I will explain in an overview manner our current understanding on phase transitions for random constraint satisfaction problems and for random graph matching problems.  Through these examples, I wish to convey the rich interplay between information and computing, as well as to emphasize the phenomenon of information-computation gap. While I aim to explain the global picture of this topic, the selection of examples is inevitably biased by my own research interests.

This talk surveys the collective accomplishments by the community; the small fraction of the material in which I am involved,  is based on joint works with Hang Du, Shuyang Gong, Zhangsong Li, Zongming Ma, Allan Sly, Nike Sun, Yihong Wu and Jiaming Xu in various combinations and in various stages.