Probability and Analysis Seminar: New lower bounds for sphere packings and independent sets via randomness

We construct new lower bounds for sphere packings in high dimensions and for independent sets in graphs with not-too-large co-degrees. For dimension d, this achieves a sphere packing of density (1 + o(1)) d log d / 2^(d+1). In general dimension this provides the first asymptotically growing improvement for sphere packing lower bounds since Rogers' bound of c*d/2^d in 1947. The proof amounts to a random (very dense) discretization together with a new theorem on constructing independent sets on graphs with not-too-large co-degree. Both steps will be discussed and no knowledge of sphere packings will be assumed or required. Central to the analysis is the study of a random process on a graph. This is based on joint work with Marcelo Campos, Matthew Jenssen and Julian Sahasrabudhe.