Time: Wed 11-12:30 and Fri 14-15:30 (@ TIFR) and TBD (@ IMSc)
Location: A-212 (@ TIFR) and TBD (@ IMSc)
Instructors: &
(TIFR) /
&
(IMSc)
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm
Communication complexity studies how much information two (or more) parties need to communicate with each other in order to compute a function, when the input is distributed across the parties. This simple mathematical model (introduced by Yao in 1979) provides an abstract framework to study the complexity of problems arising in diverse contexts (e.g., data structures, parallel and VLSI computation, game theory, circuit complexity, space bounded computation, streaming etc.), and has over the years, become an important part of the theoretical computer scientist's toolkit.
In this course, we will discuss the classical results in communication complexity and also cover the recent developments and important open problems. We will discuss different models of communication complexity---deterministic, nondeterministic, asymmetric, randomized, and multiparty, quantum---and their inter-relationship. The introductory part of the course will illustrate how problems in seemingly different contexts are modeled as communication complexity problems, and how lower bounds for the communication problem translates to lower bounds in the original context. A large part of the course will devoted to combinatorial, algebraic and information theoretic techniques for showing communication complexity lower bounds, i.e., for showing that certain functions cannot be computed without a lot of communication, when the entire input is not available at one place.
Instructors: , , &
| Prahladh Harsha |
|