Seminar Talk

Computation in high-dimensional spaces has become a critical bottleneck in data science. Even classically solved tasks, such as clustering and linear programming, are becoming intractable on modern datasets. As classical intuition and algorithms break down, the development of new mathematical approaches is required. Two core topics will be discussed: graph embeddings and integer geometry of polytopes.

1. When can a graph be embedded into a low-dimensional normed space? In recent work, we develop new combinatorial and probabilistic approaches and resolve a number of long-standing questions in this area. Applications include dimension reduction, fast data structures, and unexpected advances in the Ribe program of metric geometry.

2. How many integer points does a high-dimensional polytope contain, and how are they arranged? We focus on random models, encoding "typical" problem instances, that arise in training neural nets and rounding of integer programs. Using a combination of ideas from statistical physics, geometric analysis, and probabilistic combinatorics, we obtain strikingly detailed analysis. This has led to the discovery of several unexpected phenomena in algorithmic discrepancy minimization and the theory of sharp thresholds.