Lower
Bounds of Communication Complexity by Information
Complexity
By
-
Prof.
Shengyu Zhang
-
Assistnat
Professor, Department of Computer Science
and Engineering
-
The
Chinese University of Hong Kong
-
|
|
Date:
June 30, 2009
|
|
Time:
3:00pm - 5:00 pm
|
|
Venue:
Rm. 121, Ho Sin Hang Engineering Building, CUHK
|
Abstract
:
Information
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).
- Information
Statistics Approach to Data Stream and Communication
Complexity, Bar-Yossef, Jayram, Kumar, Sivakumar,
FOCS'02, JCSS'04.
- Two
Applications of Information Complexity, Jayram,
Kumar, Sivakumar, STOC'03.
- Lower
bounds on the randomized communication complexity
of read-once functions, Leonardos, Saks, CCC'09.
|
