Bounds in Communication Complexity
of Computer Science and Engineering
Chinese University of Hong Kong
April 9, 2009
4:30pm - 5:30 pm
Rm. 1009, William M.W. Mong Engineering Building,
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.