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. |
