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

---

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.