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.