[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SEMINAR

Tuesday, February 19, 2013
3:00 p.m.
Ryerson 251
 
Denis Pankratov              
University of Chicago
www.cs.uchicago.edu/people/pankratov
 
Title:  From Information to Exact Communication
 
Abstract: We develop a new characterization of the zero-error information complexity for two-party communication problems, and use it to compute  the exact internal and external information complexity of the 2-bit AND function. Respectively, it is 1.4923… and 1.5839… bits.This leads to a tight characterization (up to sub linear terms) of the communication complexity of the set intersection problem, whose randomized communication complexity tends to 1.4923… n +o(n) as the error tends to zero.
 
The information-optimal protocol for AND we present has an infinite number of rounds. We show that this is necessary by proving that the rate of convergence of the r-round information cost of AND to 1.4923… behaves like 1/r^2.
 
We further obtain exact communication complexity (up to sub linear terms) of  the set disjointness with error tending to 0. Our rate of convergence results imply that an optimal protocol for the set disjointness will have to use super-constant number of rounds of communication.
 
Joint work with Mark Braverman, Ankit Garg, and Omri Weinstein.

 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130219/ec562a51/attachment.htm