Density evolution and cavity method for computer science

After interesting discussions on the topic with colleagues, I decided to share a report that I wrote two years ago for Nisheeth Vishnoi’s course. The main goal of the study is going to predict analytically two phase transitions for the random XORSAT model in the limit of large systems. Most of the ideas in this document are extracted from Marc Mezard’s book Information, Physics and Computation and are only a reformulation of several chapters.

We are going use the so-called density evolution method to analyse a phase transition between to regimes, one where BP-like algorithms perform well, and a second regime where BP algorithm converge to uncontrolled local minimas. We then going use the 1RSB cavity method, which lets us predict the SAT - UNSAT threshold for the random XORSAT model.

PDF Document