Theory Lunch Seminar

  • Ph.D. Student
  • Department of Computer Science
  • Princeton University

Exact Communication Bounds for Disjointness

We determine the exact communication complexity of disjointness up to low order terms in the near zero-error regime. This is done by computing the exact zero-error information complexity of the 2-bit AND function. Towards this end, we develop a new local characterization of the zero-error information complexity function for two party communication problems.

Joint work with Mark Braverman, Denis Pankratov and Omri Weinstein.

About the Speaker.

For More Information, Please Contact: