Random Constraint satisfaction problems

Thời gian: 10:00 đến 12:00 Ngày 14/08/2017

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

Báo cáo viên: Vũ Lân (http://www.math.harvard.edu/~vinguyen/)

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. 
Refs: 

Maths:

	1. Maximum independent sets on random regular graphs. 
		Nike Sun,  Jian Ding and Allan Sly.Acta Math. 217:2 (2016). 
	2. Proof of the satisfiability conjecture for large k. 
	    Nike Sun,  Jian Ding and Allan Sly.
		
CS, Combinatorics: 

	1. Amin Coja-Oghlan, Konstantinos Panagiotou: The asymptotic k-SAT threshold. Advances in Mathematics
288:985-1068. 
	2. Amin Coja-Oghlan, Charilaos Efthymiou: On independent sets in random graphs. Random Structures and
Algorithms 47:436-486.
	
Physics:

	 1. Information, Physics, and Comutation. Marc Mezard, Andrea Montanari.
	 2. A. Braunstein, M. Mézard, M. Weigt, R. Zecchina, Constraint Satisfaction by Survey Propagation,
	 Volume on Computational Complexity and Statistical Physics, Oxford University Press (2003).
	 3.S. Mertens, M. Mézard, R. Zecchina, Threshold values of Random K-SAT from the cavity method, Random Structures and Algorithms 28 (2006) 340-373