|COMPUTER SCIENCE/DISCRETE MATH II|
|Topic:||An Algorithmic Proof of Forster's Lower Bound|
|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.