Theory Lunch Seminar

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

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:

ssingla [atsymbol] cmu.edu