Course description
How many bits must two (or more parties) communicate to compute a
function of their collective data? This fundamental problem of
communication complexity, besides being of independent interest, has
emerged as a standard tool for establishing
lower bounds for computation complexity, circuit complexity, memory
requirements for streaming algorithms and many more problems in
theoretical computer science. E2206 is a graduate level course aimed at introducing communication
complexity to information theorists. In
addition to covering the basic concepts,
special emphasis will be placed on the use of
information theoretic techniques. In
particular, we shall cover the recent
developments based on relating information
complexity to communication complexity.
- Deterministic communication complexity; Randomized communication complexity
- Distributional communication complexity; Yao’s minimax theorem
- Interactive data compression and function computation
- Variable partition model: Computation over networks and Complexity of implementing VLSI circuits
- Set disjointness: Space complexity of streaming algorithms
- Communication complexity of relations: Circuit complexity
- Lower bounds for deterministic communication complexity
- Reduction based lower bounds
- Partition lower bound
- Information complexity based lower bounds
References
- E. Kushilevitz and N. Nisan,
Communication Complexity,
Cambridge University Press, 1997.
- We will draw most of the material from
research papers and online lecture notes.