
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
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 fugacity $lambda_c(d) < lambda < lambda_c(d) + varepsilon(d)$ where $$lambda_c = frac{(d1)^{d1}}{(d2)^d}$$ is the uniqueness threshold on the $d$regular tree and $varepsilon(d)>0$ is a positive constant. Weitz produced an FPTAS for approximating the partition function when $0<lambda < lambda_c(d)$ so this result demonstrates that the computation threshold exactly coincides with the statistical physics phase transition thus confirming the main conjecture of [MWW, '09]. We further analyze the special case of $lambda=1, 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= 24$.
Our proof is based on specially constructed random bipartite graphs which act as gadgets in a reduction to MAXCUT. Building on the involved second moment method analysis of cite{MWW:09} and combined with an analysis of the reconstruction problem on the tree our proof establishes a strong version of ``replica'' method heuristics developed by theoretical physicists. The result establishes the first rigorous correspondence between the hardness of approximate counting and sampling with statistical physics phase transitions.