Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989] FPTAS for graphs with bounded max-degree [Bayati et al,STOC 2007] hardcore (independent set)
Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] • hardcore (independent set) computing the partition function
Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989] FPTAS for graphs with bounded max-degree [Bayati et al,STOC 2007] hardcore (independent set) FPRAS for counting independent sets (=1)of graphs with max-degree <4 [Dyer,Greenhill 2000;Vigoda 2001]
Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] • hardcore (independent set) • FPRAS for counting independent sets (λ=1) of graphs with max-degree ≤4 [Dyer, Greenhill 2000; Vigoda 2001] computing the partition function
Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989] FPTAS for graphs with bounded max-degree [Bayati et al.STOC 20071 hardcore (independent set) FPRAS for counting independent sets (=1)of graphs with max-degree <4 [Dyer,Greenhill 2000;Vigoda 2001] FPTAS for graphs with max-degree d when <e(d-1) [Weitz.STOC 2006]
Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] • hardcore (independent set) • FPRAS for counting independent sets (λ=1) of graphs with max-degree ≤4 [Dyer, Greenhill 2000; Vigoda 2001] • FPTAS for graphs with max-degree d when λ<λc(d-1) [Weitz, STOC 2006] computing the partition function
Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989] FPTAS for graphs with bounded max-degree [Bayati et al,STOC 2007] hardcore (independent set) FPRAS for counting independent sets (=1)of graphs with max-degree <4 [Dyer,Greenhill 2000;Vigoda 2001] FPTAS for graphs with max-degree d when A<c(d-1) [Weitz,STOC 2006] dd uniqueness threshold:Xc(d)=(d-1)4+1
Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] • hardcore (independent set) • FPRAS for counting independent sets (λ=1) of graphs with max-degree ≤4 [Dyer, Greenhill 2000; Vigoda 2001] • FPTAS for graphs with max-degree d when λ<λc(d-1) [Weitz, STOC 2006] uniqueness threshold: computing the partition function c(d) = dd (d 1)d+1
Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989] FPTAS for graphs with bounded max-degree [Bayati et al,STOC 2007] hardcore (independent set) FPRAS for counting independent sets (=1)of graphs with max-degree <4 [Dyer,Greenhill 2000;Vigoda 2001] FPTAS for graphs with max-degree d when A<Ac(d-1) [Weitz,STOC 2006] dd uniqueness threshold:λc(d④=(d-l)d+ 】 inapproxamable if >e(d-1)[Sly,FOCS 2010;Sly,Sun, FOCS 20121
Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] • hardcore (independent set) • FPRAS for counting independent sets (λ=1) of graphs with max-degree ≤4 [Dyer, Greenhill 2000; Vigoda 2001] • FPTAS for graphs with max-degree d when λ<λc(d-1) [Weitz, STOC 2006] • inapproxamable if λ>λc(d-1) [Sly, FOCS 2010; Sly, Sun, FOCS 2012] uniqueness threshold: computing the partition function c(d) = dd (d 1)d+1