Abstract: An error-correcting code is locally testable (LTC) if there is a random tester that reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it. A long-standing problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance.

Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind. We construct such codes based on what we call (Ramanujan) Left/RightCayley square complexes. These objects seem to be of independent group-theoretic interest. The codes built on them are 2-dimensional versions of the expander codes constructed by Sipser and Spielman (1996).

The main result and lecture will be self-contained. But we hope also to explain how the seminal work of Howard Garland (1972) on the cohomology of quotients of the Bruhat-Tits buildings of p-adic Lie group has led to this construction (even though it is not used at the end). Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes.

Picture a collection of hyperplanes in d-dimensional Euclidean space. These divided space into chambers (points not on any of the hyperplanes) and faces (points on some hyperplanes). The geometry and combinatorics of such arrangements is a world of its own, with applications in topology,algebraic geometry and every kind of algebra. I'll supplement this by introducing a simple family of random walks on the chambers. These include classical walks (Ehrenfest urn, card shuffling, dynamic storage allocation) but also lots of fresh examples(walks on parking functions!). Strangely, in more or less complete generality, there is a complete theory (all eigenvalues of the associated transition operators and sharp rates of convergence to stationarity--known). Naturally, there are open problems-- Understanding the stationary distribution of these walks involves the classical problem of sampling from an urn without replacement in various guises and there is a lot we don't know. I'll try to explain all this to a non-specialist audience.