Georgia Institute of Technology College of Sciences

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.