A computational phase transition for pressure approximation

In this talk, we will review some new techniques and limitations for achieving efficient approximation algorithms for entropy and pressure in the context of Gibbs measures defined over countable groups. Our starting point will be a deterministic formula for the Kolmogorov-Sinai entropy of measure-preserving actions of order-able amenable groups. Next, we will review techniques based on random orderings, mixing properties of Markov random fields, and percolation theory to generalize previous work. As a by-product of these results, we will obtain conditions for the uniqueness of the equilibrium state and the locality of pressure, among other implications that are not strictly algorithmic.