Structure vs. Randomness (Part 1)

Zander Kelley introduces the structure versus randomness paradigm, explaining how mathematical objects can be decomposed into structured and pseudorandom parts.

Zander Kelley (University of Illinois Urbana-Champaign) simons.berkeley.edu/talks/zander-kelley-university-illinois-… ICM 2026 Satellite Conference: Spectral Theory, High-Dimensional Expansion, and Pseudorandomness We will discuss the structure versus randomness paradigm: the idea that an arbitrary mathematical object (like a graph, function, or set) can often be decomposed into a usefully structured part and a certifiably pseudorandom part. In contrast to problems centered on the explicit construction of pseudorandom objects, here the objects are given to us, and the task is to find the pseudorandomness inside them. The first part of the lectures will be about how this is done, starting with Roth's theorem on three-term arithmetic progressions and then looking at density increment and regular decomposition arguments more generally. In the second part, we will discuss the problem of comparing two given notions of pseudorandomness and understanding how they relate, for instance by way of inverse theorems. This turns out to occupy much of the subject, in part because the notions we are forced to work with when finding pseudorandomness in arbitrary objects are relatively weak ones.