# CSAIL Event Calendar: Previous Series

 Correspondence of Computational and Statistical Physics ThresholdsSpeaker: Allan Sly , Microsoft ResearchDate: October 5 2010 Time: 4:15PM to 5:15PM Location: 32-144Host: Scott Aaronson, CSAIL, MITContact: Be Blackburn , 3-6098, imbe@mit.eduRelevant URL: I'll discuss the problem of approximately counting independent sets in sparse graphs and its relationship to the hardcore model from statistical physics. The hardcore model is the probability distribution over independent sets I of a graph weighted proportionally to \lambda^{|I|} with parameter 0<\lambda<\infty. We prove that at the "uniqueness threshold" of the hardcore model on the d-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree d. Specifically, we show that unless NP=RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree d for \lambda_c(d) < \lambda < \lambda_c(d) + \epsilon where \lambda_c(d) is the uniqueness threshold on the d-regular tree. Weitz produced an FPTAS for approximating the partition function when 0<\lambda <\lambda_c(d) so this result demonstrates that the computational threshold exactly coincides with the statistical physics phase transition thus confirming the main conjecture of Mossel, Weitz and Wormald. We further analyze the special case of \lambda=1 and d=6 and show there is no polynomial time approximation scheme for approximately counting independent sets on graphs of maximum degree d= 6, which is optimal, improving the previous bound of d= 25.See other events that are part of Theory Colloquium 2010/2011See other events happening in October 2010