Bounds of Communication Complexity by Information
Professor, Department of Computer Science
Chinese University of Hong Kong
June 30, 2009
3:00pm - 5:00 pm
Rm. 121, Ho Sin Hang Engineering Building, CUHK
complexity is a new approach to lower bounding communication
complexity. I'll introduce this method, covering the
proof for the Disjointness function (the first paper
below), Tribes function (the second paper below) and
mentioning the main result of the general read-once
formula (the third paper below).
Statistics Approach to Data Stream and Communication
Complexity, Bar-Yossef, Jayram, Kumar, Sivakumar,
Applications of Information Complexity, Jayram,
Kumar, Sivakumar, STOC'03.
bounds on the randomized communication complexity
of read-once functions, Leonardos, Saks, CCC'09.