Course Material:
The first part of the course follows the book
Communication Complexity by Eyal Kushilevitz and Noam Nisan.
Lecture notes will be published for the rest of the course.
- Part I: combinatorial and algebraic lower bounds
- Lecture 1: introduction to communication complexity; fooling set lower bound (section 1.3);
Karchmer-Wigderson games and monotone circuit lower bound for matching (sections 10.1 - 10.3).
- Lecture 2: rectangle size lower bound (section 1.3); rank lower bound and the log rank conjecture (section 1.4);
nondeterministic communication complexity and relation to monochromatic covers (section 2.1);
deterministic vs. nondeterministic communication complexity (section 2.3).
- Lecture 3: communication complexity of k-disjointness (example 2.12);
randomized vs. deterministic communication complexity (section 3.2);
public-coin vs. private coin (section 3.3);
Yao's minimax principle and distributional communication complexity (section 3.4).
- Lecture 4: discrepancy bound (section 3.5); randomized communication complexity
of inner product (example 3.29); corruption bound; randomized communication complexity of set disjointness
under product distributions (see "The story of set disjointness", a SIGACT News Column by Chattopadhyay and Pitassi);
streaming lower bounds using communication complexity (see
"The space complexity of approximating the frequency moments" by Alon, Matias and Szegedy).
- Part II: information complexity
- Part III: applications and advanced topics
- Lecture 9: streaming lower bounds using communication complexity;
index lower bound using information complexity; reduction from index to gap hamming distance (see "The one-way communication complexity of Gap Hamming Distance" by Jayram, Kumar and Sivakumar).
Introduction to the number-on-forehead model and its application in circuit lower bounds.
Homework:
To be submitted in writing/print at the end of class.
You may discuss the homework with other students but each student must write their solutions
alone. Indicate at the top of your submission who you discussed the homework with.
Final projects:
Syllabus:
- Communication complexity:
lower bound techniques for deterministic and randomized
protocols;
rectangle covers;
nondeterministic communication complexity;
Razborov's lower bound for Disjointness;
applications.
- Information complexity:
definitions and relationship to communication;
direct sum;
the BJKS'04 lower bound for Disjointness;
compression.
- Advanced topics and applications:
streaming lower bounds;
Sherstov's lower bound for Gap Hamming Distance;
data structure lower bounds in the cell-probe model;
circuit and formula lower bounds and number-on-forehead multi-party communication;
the Babai-Nisan-Szegedy lower bound for Generalized Inner Product;
applications in distributed computing;
other topics.