The cavity method

To solve the mean-field theory of spin glasses, Giorgio Parisi used the replica method, which still retains its share of mystery.To understand its content, and find an alternative solution that was more physical and better mathematically controllable, we devised with Parisi and Virasoro a completely different approach, the cavity method. While this approach has led to a rigorous solution of the problem, it has also enabled us to develop new types of algorithms for difficult optimization problems involving a large number of variables, such as the famous " SAT problem ", which lies at the heart of algorithmiccomplexity theory. This seminar aims to summarize these different aspects of the cavity method.