Lower Bounds in Communication Complexity

By

Prof. Shengyu Zhang

Department of Computer Science and Engineering
The Chinese University of Hong Kong

Date: April 9, 2009

Time: 4:30pm - 5:30 pm

Venue: Rm. 1009, William M.W. Mong Engineering Building, CUHK

Abstract :

Communication complexity studies the minimum amount of communication required to compute a function with input distributed in different parties. Since its invention 30 years ago, it has found applications in numerous other areas in theoretical computer science. In most of the applications, communication complexity serves as a powerful lower bound method, which implies that lower bounds for communication complexity itself are very important. In this seminar I'll talk about some recent progress of this area.