CS 289 Communication Complexity

 
Instructor   Alexander Sherstov
Email   my last name at cs.ucla.edu
Quarter   Spring 2018
Lecture   F 2–5:50pm (BOELTER 4413)
Office Hours F 1:30–2pm (ENGINEERING VI, Room 465)
F 5:50–6:20pm (BOELTER 4413)
Webpage http://www.cs.ucla.edu/~sherstov/teaching/2018-spring
Textbook E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press, 2nd edition, 2006.

Description

Consider a function f whose arguments are distributed among several parties, making it impossible for any one party to compute f in isolation. Communication complexity theory studies how many bits of communication are needed to evaluate f. A trivial approach is for the parties to communicate their inputs to each other. While this costly solution is optimal in some cases, one can often accomplish the task with surprisingly little communication. To cite a famous example, one can check with accuracy 99% if two geographically separated databases are identical by communicating only eight bits, regardless of how large the databases actually are! Over the past three decades, communication complexity has evolved into a central area of theoretical computer science, with deep open questions, beautiful mathematics, and many applications.

This graduate course is a self-contained introduction to communication complexity, with coverage of the fundamentals, key classic theorems, and current research directions. It is a rigorous and mathematically demanding course, with an emphasis on proofs. Mathematical maturity is assumed.

Grading

Course Schedule

The course schedule below is tentative and may be adjusted in response to student interest and time constraints.

  1. DETERMINISTIC COMMUNICATION
  2. NONDETERMINISM
  3. RANDOMIZED COMMUNICATION
  4. GEOMETRIC METHODS
  5. SPECTRAL METHODS
  6. QUANTUM COMMUNICATION

Problem Sets

You have a week to complete each problem set. Your write-up must be typeset rather than handwritten. I recommend using LaTeX for this purpose. If you are new to LaTeX, you may find it easier to create your document in a user-friendly integrated environment such as Kile or Lyx.

Problem set I Problem set II

Policies