The course will follow the classic textbook of Kushilevitz and Nisan in part, and include newer material in part.
The lecture notes cover all material which was presented.
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): Derandomization of ZPP. Greater-Than is not in RP. Distributional complexity and its relation to randomized complexity. Discrepancy method.
- Week 7 (11 June 2026): Discrepancy lower bound for Inner Product. Discrepancy fails for Set Disjointness. Corruption bound. Equality does not simulate randomness.
- Week 8 (18 June 2026): Approximate rank and sign rank. Lower bound on the sign rank of Set Disjointness. Pointer jumping.
- Week 9 (25 June 2026): Multiparty communication complexity. Grolmusz’ protocol for generalized inner product. Discrepancy lower bound. ExactlyN and Ramsey theory.
- Week 10 (2 July 2026): Query complexity: deterministic, nondeterministic, randomized, degree. Deterministic is at most quadratic in nondeterministic. Tightness example. Deterministic is at most cubic in randomized.
- Week 11 (9 July 2026): Query complexity: deterministic is at most cubic in degree. Quadratic tightness example. Unbounded-error randomized query complexity is sign degree. Sign degree of parity.
- Week 12 (16 July 2026): Lifting inside query complexity: depth to size (via random restriction, via simulation), depth to parity size (via simulation). Nondeterministic query-to-communication lifting.
