Codes, Szemerédi's theorem and upper tails
This talk is about three problems and a common feature that connects them. The three problems concern 1. special types of error correcting codes (known as locally decodable codes), 2. random differences in Szemerédi's theorem on arithmetic progressions (more precisely, intersective sets, a.k.a. recurrent sets) and 3. upper tail estimates for the number of edges induced by a random vertex subset of a given hypergraph. The common feature lurking beneath them concerns the average (Gaussian) width of special configurations of points in high-dimensional Euclidean space. The aim for this talk is to explain what the three problems are about, mention some of their history and say what bounds on Gaussian widths imply for them. This is based on joint work with Sivakanth Gopi.