Spatial Mixing of Coloring q-coloring of G q≥0d+O(1) max-degree:d SSM:>1.763.. (solution to x=e) average degree? [Goldberg,Martin,Paterson 05]triangle-free amenable graphs [Ge,Stefankovic 11]regular tree [Gamarnik,Katz,Misra 12]triangle-free graphs Spatial-mixing-based FPTAS: ● [Gamarnik,Katz 07]>2.8432...,triangle-free graphs [Lu,Y.14]0>2.58071.. SSM→algorithm [Goldberg,Martin,Paterson 05]amenable graph,SSM=FPRAS [Y.,Zhang 13]planar graph (apex-minor-free),SSM=FPTASSpatial Mixing of Coloring • [Goldberg, Martin, Paterson 05] triangle-free amenable graphs • [Ge, Stefankovic 11] regular tree • [Gamarnik, Katz, Misra 12] triangle-free graphs q-coloring of G q ≥αd+O(1) max-degree: d • [Goldberg, Martin, Paterson 05] amenable graph, SSM 㱺 FPRAS • [Y., Zhang 13] planar graph (apex-minor-free), SSM 㱺 FPTAS • [Gamarnik, Katz 07] α>2.8432..., triangle-free graphs • [Lu, Y. 14] α>2.58071... SSM: α>1.763... xx (solution to ) = e SSM 㱺 algorithm Spatial-mixing-based FPTAS: average degree?