Results sufficient conditions for FPTAS for classes of spin systems coloring:q≥ox△+β randomized algorithms:by simulating a random walk (the Glauber dynamics)over colorings a=11/6 (Jerrum'95Bubley-Dyer'97+Vigoda'99) deterministic algorithms:by exploiting the correlation decay (spatial mixing)property .8432 (Gamarnik-Katz'07) just correlation decay(no FPTAS):a~1.763 (Goldberg-Martin-Paterson'05,Gamarnik-Katz-Misra'12) this paper:deterministic FPTAS for a2.58071Results • coloring: q ≥αΔ+β • randomized algorithms: by simulating a random walk (the Glauber dynamics) over colorings • α=11/6 (Jerrum’95⇢Bubley-Dyer’97⇢Vigoda’99) • deterministic algorithms: by exploiting the correlation decay (spatial mixing) property • α≈2.8432 (Gamarnik-Katz’07) • just correlation decay (no FPTAS): α≈1.763 (Goldberg-Martin-Paterson’05, Gamarnik-Katz-Misra’12) sufficient conditions for FPTAS for classes of spin systems this paper: deterministic FPTAS for α≈2.58071