Random constraint problem and Statistical physics

Thời gian: 15:30 đến 17:00 Ngày 11/03/2019

Địa điểm: B4-705, VIASM

Báo cáo viên: Dr. Nguyễn Vũ Lân, Bonn University

Tóm tắt:

Constraint satisfaction problems such as graph coloring and boolean satisfiability are fundamental for understanding computational complexity and certain physical processes. Randomly generated instances of these problems are known to have intricate probabilistic structure, and recent work has made good progress in uncovering this structure. In this informal talk, we will consider the K-SAT problem and maximum independent set on random regular graphs.