Structure vs. Randomness (Part 2) @SimonsInstitute
Structure vs. Randomness (Part 2)  @SimonsInstitute
Uploaded August 2026 | Updated November 2026, 1 day ago
Zander Kelley (University of Illinois Urbana-Champaign)
https://simons.berkeley.edu/talks/zander-kelley-university-illinois-urbana-champaign-2026-08-28
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.
Structure vs. Randomness (Part 2)Graphs versus Manifolds in Eigenvalues and Distances Between SubsetsDerandomizing Space-Bounded Computation (Part 1)Probability, Information, and DiscrepancyCondensers/extractors for block sources surveyStrongly explicit sorting on HDXsQuantifying Reliability in AI: Hallucinations and UncertaintySpectral approximation of directed graphs and moreHigh-Accuracy Sampling for Diffusion Models and Log-Concave DistributionsExplicit free expandersScore-Based Generative Modeling without Diffusion: Langevin MCMC All the WayThe Computer in the Sky | Theoretically Speaking
Simons Institute for the Theory of Computing |

Structure vs. Randomness (Part 2)

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER