Random constraint problem and Statistical physics

Time: 15:30 to  17:00 Ngày 11/03/2019

Venue/Location: B4-705, VIASM

Speaker: Dr. Nguyễn Vũ Lân, Bonn University

Content:

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.