Theory Bubbles

A fact that was initially surprising to me is that stochastic differential equations can actually be useful in solving discrete problems. The Lovett–Meka proof of Joel Spencer’s classic discrepancy theorem is an elegant showcase of this idea. Today we will discuss Spencer’s theorem and a proof based on Brownian motion! Spencer's theorem. Let \(A\) be an \(n \times n\) matrix with entries in \([-1,1]\). Then there is a vector \(x \in \{\pm 1\}^n\) such that ...

John’s ellipsoid theorem is a clean high-dimensional convex geometry fact that shows up in a lot of different places. Informally, it says: Every $n$-dimensional symmetric convex body is an ellipsoid, up to a $\sqrt n$ scaling. This is quite nice and convenient because ellipsoids are basically “$\ell_2$” objects, which makes them a lot easier to do math with than arbitrary convex bodies. There is a long list of applications of John’s theorem that I won’t cover here, but it recently came up for me in three different contexts. ...