Rationality and computability of the covering radius for sofic shifts

The covering radius of a shift space is a quantity of interest for information-theoretic applications of data transmission over noisy channels. In this talk we will explain what is the covering radius of a sofic shift and why people care about it. We will outline a proof that the covering radius of a primitive sofic shift is always a rational number, and outline an algorithm to compute the covering radius from a labeled graph presentation. We will also briefly explain how these results relate to dynamics, to a certain zero-sum two-player game and to an old meta-conjecture about typical ground states in statistical mechanics. The notions will be defined, no specific background assumed. Based on joint work with Aidan Young as in https://arxiv.org/abs/2603.21449, and previous joint work with Dor Elimelech and Moshe Schwartz as in https://ieeexplore.ieee.org/document/10360152