Speaker: Brian Marcus

Title: Polynomial time approximation of entropy of multi-dimensional shifts of finite type

Abstract: In one dimension, there is an explicit general formula known for the topological entropy of a shift of finite type (SFT).  No such formula is known for higher dimensional SFT's, and the exact entropy is known for only a handful of examples. Lind's characterization of the set of entropies in one dimension in terms of Perron numbers is much different from the Hochman-Meyerovitch characterization in higher dimensions in terms of right recursively enumerable (RRE) numbers. While RRE numbers can be arbitrarily poorly computable, some higher dimensional SFT's have entropy which is computable in polynomial time, meaning that there is an algorithm which on input n, gives an approximation that is computed in time polynomial in n and is accurate to within 1/n.

After giving some background, we will focus on a method of proving computability of entropy in polynomial time for certain SFT's. The method makes use of measures of maximal entropy. We first give conditions that guarantee that the entropy is the average value of the information function of a measure of maximal measure theoretic entropy over a single periodic orbit.  With stronger conditions we show how to efficiently approximate these values and thus efficiently approximate the entropy. The method naturally extends to approximation of the pressure (free energy) of certain nearest neighbour interactions that arise in statistical physics and is an outgrowth of a method introduced by Gamarnik and Katz. The talk will be based on joint papers with Stefan Adams, Raimundo Briceno and Ronnie Pavlov.