The course will closely follow the classic textbook of Kushilevitz and Nisan.
Here are some lecture notes, which also include some material beyond the textbook.
Material covered:
- Week 1 (16 April 2026, via zoom): What is communication complexity. Some applications, including a time-space tradeoff for Turing machines. Definition of two-party deterministic communication complexity. Combinatorial rectangles, and partition number as a lower bound on deterministic communication complexity. (Corresponds to Sections 1, 2.1, 2.2 of the book.)
- Week 2 (23 April 2026, via zoom): Review of Week 1. Fooling set lower bound. Lower bound using maximal area or measure of monochromatic rectangle. Rank lower bound. (Corresponds to the rest of Section 2 in the book.)
- Week 3 (14 May 2026): Review of Weeks 1 and 2. Rank lower bound in more detail. Log rank conjecture. Protocol partition number, and protocol balancing. Comparison to other settings (formulas, decision trees). Covering number.
- Week 4 (18 May 2026): Measure bound as a lower bound on covering number. Almost matching upper bound, and gap example. Nondeterministic complexity. Deterministic complexity is bounded by the product of nondeterministic and co-nondeterministic complexity. Tightness example.
- Week 5 (28 May 2026): Randomized complexity. Examples. Error reduction. Simulation of randomized protocols by deterministic protocols. Newman’s theorem.
- Week 6 (4 June 2026): Randomized complexity.
