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.