When do random CSPs become hard?

SIAM Student Seminar
Friday, October 29, 2010 - 13:05
1 hour (actually 50 minutes)
Skiles 255
School of Mathematics, Georgia Tech
A constraint satisfaction problem (CSP) is an ensemble of boolean clauses, where satisfaction is obtained by an assignment of the variables if every clause is satisfied by such assignment. We will see that when such CSP is arranged following certain random structure, the Fourier expansion of the corresponding clauses allows us to understand certain properties of the solution space, in particular getting a partial understanding of when the 'usual suspects' of the drastical failure of all known satisfiability algorithms, namely long range correlations and clustering, appear. Based in joint work with Prasad Tetali and Andrea Montanari.