Date

Topic

Readings

Exercises

Notes

Sep 7
Introduction; Class overview;
Examples of communication protocols;
and the two-party deterministic model
CC Book Chapter 1
Chapter 13 of Computational Complexity
A Modern Approach, by Arora and Barak
Some complexity questions related to distributive
computing, by Yao
Exercise 1
Note 1
by Xiaorui Sun
Sep 12
Fooling sets and Rectangle size
Rank lower bound
CC Book Chapter 1
Chapter 13 of Computational Complexity
A Modern Approach, by Arora and Barak
Exercise 2
Note 2
by Igor Carboni Oliveira
Sep 14
Covers and nondeterminism
Determinism versus nondeterminism
CC Book Chapter 2
Exercise 3
Note 3
by Igor Carboni Oliveira
Sep 19
Communication complexity of relations
Karchmer-Wigderson games
Khrapchenko's bound
CC Book Section 5.1, 10.1 and 10.2

Note 4
by Timothy Sun
Sep 21
Lower bound for the FORK relation
CC Book Section 5.3
Exercise 4

Sep 26
Randomized communication complexity
Public coin vs Private coin
Distributional complexity
CC Book Section 3.1, 3.3 and 3.4
Note on the minimax theorem
Lecture Notes on Linear Duality By Trevisan
Exercise 5

Sep 28
The discrepancy method
Lower bound for IP
CC Book Section 3.5
Exercise 6

Oct 3
Lower bound for Disjointness with
a product distribution
A public-coin protocol for Disjointness
with sets of size k
Complexity Classes in Communication Complexity
Theory, by Babai, Frankl and Simon.
The Randomized Communication Complexity of Set
Disjointness, by Hastad and Wigderson


Oct 5
Linear lower bound for Disjointness
CC Book Section 3.4 and 4.6


Oct 10
Linear lower bound for Disjointness
Direct sum for nondeterministic and
deterministic communication complexity
CC Book Section 4.6 and 4.1
Exercise 7

Oct 13
Multiparty communication complexity
Cylinder intersection
CC Book Section 6.1 and 6.2


Oct 17
Discrepancy lower bound and GIP
CC Book Section 6.4


Oct 19
Time-space tradeoffs for Turing machines
Variable partition models
Width-length tradeoffs for branching programs
CC Book Chapter 7 and Chapter 12
Exercise 8

Oct 31
Width-length tradeoffs (cont.)
VLSI lower bounds
Application in combinatorial auctions
CC Book Section 8.3
Algorithmic Game Theory Section 11.1 and 11.6
Exercise 9

Nov 2
Lower bounds for streaming algorithms
The space complexity of approximating the
frequency moments, by Alon, Matias and Szegedy
Lower bounds on streaming algorithms for
approximating the length of the longest
increasing subsequence, by Gal and Gopalan