报告人：尹一通
报告地点：腾讯会议139-210-037
报告时间：2022年10月27日星期四下午3:00
报告题目：Optimal mixing of Gibbs sampling up to critical threshold
报告简介：
本报告将介绍Gibbs采样的“计算相变”（computational phase transition）的最新成果。关于Gibbs采样的计算复杂性，一个长期以来的猜想是：概率图模型的物理相变性质决定了依概率图模型采样的计算复杂性——这就是“计算相变”现象。这一猜想的复杂性一侧，即相变界以外采样问题是NP难的，已被严格证明，并获得FOCS ’10最佳论文奖；而这一猜想的算法一侧，即相变界以内采样问题有高效算法，却始终没有被完全解决。近年来，随着高维扩张器（high-dimensional expander）理论的发展，这一问题上也取得若干突破。我们在以硬核模型（hardcore model）为代表的一类反铁磁性（anti-ferromagnetic）概率图模型上证明了：在相变条件内Gibbs采样的最优混合（mixing），从而证明了“计算相变”猜想。
报告人简介：
尹一通，博士，教授，博士生导师，主要研究领域为理论计算机科学，包括随机算法、数据科学的计算理论基础等，在JACM、SICOMP、STOC、FOCS、SODA等重要学术期刊和会议发表论文四十余篇，主持国家重点研发计划项目，获国家自然科学基金优秀青年科学基金、CCF/IEEE CS青年科学家奖、中创软件人才奖、教育部新世纪人才、南京大学青年五四奖章、南京大学杜厦奖教金等，指导博士生获得CCF优秀博士学位论文奖。
