An Algorithmic Proof of Forster's Lower Bound

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH II
Topic:An Algorithmic Proof of Forster's Lower Bound
Speaker:Moritz Hardt
Affiliation:Princeton University
Date:Tuesday, December 15
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/forsterslowerbound

We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists.