In this talk I rigorously prove the validity of the cavity equations for
the problem of counting the number of matchings in large girth
graphs. Cavity method is an important heuristic developed by statistical
physicists that has lead to the development of faster distributed
algorithms for problems in combinatorial optimization and in coding
theory. The validity of this approach has been supported mostly by
numerical simulations.

This is joint work with Chandra Nair.