报告人：丁剑博士
报告题目：The exact k-SAT threshold for large k.
报告时间：2015年3月11日（周三下午3:30 ）
报告地点：太阳成集团学术报告厅（静远楼1506室）
报告摘要：We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k(0). That is, there exists a single critical density alpha_s(k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for alpha < alpha_s(k), and unsatisfiable for alpha > alpha_s(k). The threshold alpha_s(k) matches the explicit prediction derived by statistical physicists on the basis of the so-called `one-step replica symmetry breaking' (1RSB) heuristic. In the talk I will explain the main obstacles in computing the threshold, and describe how they are overcome in our proof. No prior background in statistical physics will be assumed.(Joint work with Allan Sly and Nike Sun)
丁剑博士简介：
Jian Ding, assistant professor at the University of Chicago, specializes in probability theory. He aims to understand mathematical structures for stochastic processes that arise naturally in statistical physics, as well as combinatorial optimization. Two main directions of his research concern solution space of random constraint satisfaction problems, as well as geometry of level sets for Gaussian processes. Jian obtained his Ph.D. from U.C. Berkeley in 2011, and spent a year at Stanford as a Szegö assistant professor before moving to University of Chicago. Jian was awarded a Sloan fellowship in 2015 and an NSF CAREER award for 2015-20.