Zrrv Dvir: A Wonderful Theorem of Barthe and its Applications in Discrete Geometry and TCS.

Friday, November 6, 2015 - 1:30pm to 4:30pm
Pizza at 1:15p
Harvard, MD, Room 119

Abstract:  In his work on the Brescamp-Leib inequality, Barthe proved a remarkably simple and useful theorem on finite sets of points in R^d. Roughly speaking, as long as the points are not `too linearly dependent' (say, no large subset belongs to a low-dimensional space) then there exists a change of basis that puts them in radial (or projective) isotropic position: meaning that their normalized unit vectors (after the basis change) are in isotropic position.  A special case of this result (for points in general position) was used by Forster to prove strong communication complexity lower bounds by bounding the sign-rank of an explicit matrix. More recently, the full result was used to derive new bounds for 3-query locally correctable codes over the reals (D., Saraf, and Wigderson) and high dimensional generalizations of the Sylvester-Gallai theorem for arrangements of subspaces (D. and Hu). In this talk I will describe the theorem and try to explain how it is used in each of these results. I will also show the proof of the theorem, which uses ideas from convex optimization.