Videos

An Algorithmic Proof of Forster's Lower Bound

Presenter
December 15, 2009
Keywords:
  • Princeton University
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
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.