Tight Bounds for Volumetric Spanners in All Norms

Explore a 37-minute lecture on volumetric spanners and their applications in various fields of computer science and mathematics. Delve into the concept of expressing a set of points using a subset with "small" coefficients, measured in appropriate norms. Examine the formal definition of volumetric spanners and their significance in areas such as bandit linear optimization, determinant maximization, and matrix low rank approximation. Learn about the almost optimal bounds on the size of volumetric spanners for all ℓ_p norms and the simple local search procedure for their construction. Discover the applications of these findings to other tasks, particularly in finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem. Gain insights from the joint work of Ali Vakilian, Aditya Bhaskara, and Sepideh Mahabadi, presented at the Simons Institute as part of the Sketching and Algorithm Design series.

Tight Bounds for Volumetric Spanners in All Norms