Test calendar

Title: Exchanges of exchangeability: limit theory, quasirandomness and high-arity learning

Abstract: The classic de Finetti's Theorem from 1931 says that an infinite sequence of random variables is invariant under permutations (exchangeable) if and only if it is a mixture of i.i.d. random variables. For a long time, this was considered a curiosity of classic probability theory. In the 80s, exchangeability was revived with the Aldous--Hoover Theorem which completely characterized exchangeable distributions of random matrices (i.e., distributions invariant under simultaneous permutations of rows and columns), and more generally tensors. Since the resulting Aldous--Hoover representation theorem yielded complicated representations, Hoover asked which distributions admitted simpler representations, called $\ell$-independent representations, and noticed that a natural assumption, called $\ell$-locality, was necessary but not sufficient.

In this talk, I will cover surprising connections of exchangeability theory with combinatorics and learning theory. In the former connection, exchangeability can be used to construct semantic/geometric limits of dense combinatorial objects, which capture the asymptotic behavior of densities of subobjects; in turn, these limit objects are used to study quasirandomness and connect back to Hoover's question on independence vs. locality.

In the latter connection, exchangeability forms the backbone of high-arity probability approximately correct (PAC) learning theory, which is a natural learning theory for learning hypergraphs. In turn, high-arity PAC learning theory can be used to obtain better bounds in tame hypergraph regularity lemmas, which connect back to Aldous--Hoover representations of low rank (a notion dual to $\ell$-independence).

No background in exchangeability theory, limit theory or learning theory is required to follow the talk.

This talk is based on several joint works with Maryanthe Malliaris, Alexander Razborov, Caroline Terry and Henry Towsner.