Theory Lunch Seminar

Ph.D. Student
Department of Computer Science
Princeton University
Exact Communication Bounds for Disjointness
Wednesday, March 19, 2014 - 12:00pm to 1:00pm
Gates&Hillman Centers

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: