Lecture 1: Where the Hard Things Are
This series of talks is part of the Counting Complexity and Phase Transitions Boot Camp.
Speaker: Andrea Montanari (Stanford University)
The study of random constraint satisfaction problems was initiated in the eighties with the objective of better understanding the generic properties of hard instances, and developing better heuristics. How much has been accomplished on the way to these objectives? I will present a review of partial results, conjectures, and open problems, emphasizing contributions from multiple research communities. I will also outline the connections between progress on this research direction and connection with 'applications' in machine learning, statistics, and information theory.