Phase transitions of random constraint satisfaction problems
主 题: Phase transitions of random constraint satisfaction problems
报告人: 丁剑教授 (Univ. of Chicago)
时 间: 2014-12-19 15:00-16:00
地 点: 理科一号楼1114（数学所活动）
I will report some recent progress on the study of random constraint satisfaction problems, with focus on the satisfiability transitions. In particular, I will present a
recent proof for the satisfiability threshold for random k-SAT for all k >= k_0 where k_0 is a fixed large constant. That is, there exists a limiting 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 satisfiability threshold alpha_s(k) is given explicitly by the one-step replica symmetry breaking prediction from statistical physics. Joint works with Allan Sly and Nike Sun.
