Computational Phase Transition hardcore model:graph G(V,E),max-degree A,fugacity >0 approx sample independent set in G w.p. λ（△）= (△-1)（△-1） [Weitz,.STOC'06:lfλ<λc,nO(log△)time. (△-2)A [Sly,FOCS'l0 best paper]:lfλ>λc, NP-hard even for A=O(1). [Efthymiou,Hayes,Stefankovic, Vigoda,Y.,FOCS'16]: max-deg△ lfλ<入c,O(n log n)mixing time. If A is large enough,and there is no small cycle. A phase transition occurs at Ac.Computational Phase Transition hardcore model: graph G(V,E), max-degree Δ, fugacity λ>0 approx sample independent set I in G w.p. ∝ λ|I| ￾c(￾) = (￾ ￾ 1)(￾￾1) (￾ ￾ 2)￾ 2 4 6 8 10 1 2 3 4 5 6 Hard Easy max-deg Δ λ • [Weitz, STOC’06]: If λ<λc, nO(log Δ) time. • [Sly, FOCS’10 best paper]: If λ>λc, NP-hard even for Δ=O(1). [Efthymiou, Hayes, Štefankovič, Vigoda, Y., FOCS’16]: If λ<λc, O(n log n) mixing time. If Δ is large enough, and there is no small cycle. A phase transition occurs at λc