Resolution of the Quadratic Littlewood-Offord problem | Research seminar in Discrete Mathematics

Abstract

Consider a quadratic polynomial $Q(\xi_{1},\dots,\xi_{n})$ of a random binary sequence $\xi_{1},\dots,\xi_{n}$. To what extent can $Q(\xi_{1},\dots,\xi_{n})$ concentrate on a single value? This is a quadratic version of the classical Littlewood-Offord problem; it was was popularised by Costello, Tao and Vu in their study of symmetric random matrices, and has since become a rich source of connections between combinatorics, probability and computer science. In this talk we will discuss a new essentially optimal bound for the quadratic Littlewood-Offord problem, as conjectured by Nguyen and Vu. Joint work with Lisa Sauermann.

Speaker Intro

Matthew Kwan completed his PhD on extremal and probabilistic combinatorics under the supervision of Benny Sudakov. Since then, he has continued working on combinatorics and its connections to probability. After an appointment as Szegő Assistant Professor at Stanford University, he is currently an Assistant Professor at the Institute for Science and Technology in Austria. In 2020 he received the SIAM Dénes Kőnig Prize, and in 2023 he received an ERC starting grant.