Sampling Counting [Jerrum-Valiant-Vazirani'86]: for all self-reducible problems approx counting exact approx sampling vol() X=(X1.X2.....X) Poly-Time Turing approx inference X~2 Machine Pr[X=·|X=o FON CNITORN ON OCNONMTORAL STUCTU Mark R.JERRUM MCMC Sampling Computational Phase Transition Markov chain for sampling =(X1.X2.....X)~ hardcore model:graph G(V,E).max-degree A,fugacity >0 ● Gibbs sampling (Glauber dynamics,heat-bath) approx sample independent set Iin Gw.p. pick a random i: [Glauber,'63] X(△)= (4-1)a-1) [Weitz,STOC'06]:If <c,no(log A)time. resample~4,(·N(v)h [Geman,Geman,'84] (△-2)A [Sly,FOCS'10 best paper]:If Metropolis-Hastings algorithm NP-hard even for A=0(1). pick a random i: [Metropolis et al,'53] Hard [Efthymiou,.Hayes,Stefankoviě， propose a random e; X-cwp.uxu(); [Hastings,'84] Easy Vigoda,Y.,FOCS'16]: If <he,O(n log n)mixing time. Analysis:coupling methods max-deg△ If A is large enough.and there is no small cycle. [Aldous,'83][Jerrum,'95][Bubley,Dyer'97] A phase transition occurs at e. may give O(n log n)upper bound for mixing time Big Data?Big Data?