Computer Science/Discrete Mathematics Seminar I | |

Topic: | Information Complexity and Exact Communication Bounds |

Speaker: | Mark Braverman |

Affiliation: | Princeton University |

Date: | Monday, December 3 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/1213/csdm/MarkBraverman-1203 |

In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the AND of two bits distributed between Alice and Bob. We prove that the information complexity of AND is ~1.4923 bits. We use the optimal protocol and its properties to obtain tight bounds for the Disjointness problem, showing that the randomized communication complexity of Disjointness on n bits is ~0.4827n ± o(n). Based on joint work with Ankit Gard, Denis Pankratov, and Omri Weinstein