On the Hard Core Model and Enumerating Independent Sets

Abstract: Seminal results of Weitz (2005) and Sly (2010) prove that one can in polynomial time approximately count independent sets in 5-regular graphs but cannot approximately count independent sets in 6-regular graphs (unless NP=RP). We discuss these results in the broader context of sampling from the hard core model and give a high level idea of the proof of each of these results.

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar