报告题目：Recent progress on random graph matching problems
报 告 人：丁剑（北京大学）
会议时间：2025年1月14日9：30开始
会议地址：九号楼113报告厅
报告摘要：A basic goal for random graph matching is to recover the vertex correspondence between two correlated graphs from an observation of these two unlabeled graphs. Random graph matching is an important and active topic in combinatorial statistics: on the one hand, it arises from various applied fields such as social network analysis, computer vision, computational biology and natural language processing; on the other hand, there is also a deep and rich theory that is of interest to researchers in statistics, probability, combinatorics, optimization, algorithms and complexity theory. Recently, extensive efforts have been devoted to the study for matching two correlated Erdős-Rényi graphs, which is arguably the most classic model for graph matching. In this talk, we will review some recent progress on this front, with emphasis on the intriguing phenomenon on (the presumed) information-computation gap. In particular, we will discuss progress on efficient algorithms thanks to the collective efforts from the community. We will also point out some important future directions, including developing robust algorithms that rely on minimal assumptions on graph models and developing efficient algorithms for more realistic random graph models. This is based on joint works with Guanyi Chen, Yumou Fei, Hang Du, Shuyang Gong, Zhangsong Li and Yuanzheng Wang.
报告人简介：丁剑于2006年获得北京大学学士学位，后赴美留学并于2011年获得美国加州大学伯克利分校统计学博士学位。他的主要研究领域是概率论，尤其关注统计物理与计算机科学的交叉。最近的研究方向包括随机约束满足问题、随机平面几何、安德森局部化和无序自旋模型。曾任芝加哥大学统计系助理教授、副教授，宾夕法尼亚大学沃顿商学院副教授、Gilbert Helman讲席教授。丁剑曾获戴维逊奖(Rollo Davidson Prize), 洛伊夫概率奖、斯隆奖(Alfred P. Sloan Fellowship)、 美国NSF Career Award、第九届世界华人数学家大会数学金奖以及科学探索奖等国内外多个重量级大奖。此外，受邀在2022年国际数学家大会作45分钟报告；在2023年作IMS Medallion Lecture；并将受邀在2024年度国际数学物理大会(ICMP2024)作大会报告。目前丁剑担任国际期刊《Journal of American Mathematical Society》, 《Annals of Probability》, 《Communication in Mathematical Physics》，《Annals of Applied Probability》,《Math Forum Pi&Sigma》等杂志编委。
