SYLLABUS

Below is a tentative syllabus for the course. This is subject to change as the course progresses.

Lecture 1: Course Introduction.
What is communication complexity? The basic model. deterministic communication complexity. the EQUALITY function. the fooling set technique.
Relevant reading: Kushilevitz/Nisan Chapter 1

Lecture 2: The Rank Lower Bound, Covers, Nondeterministic Communication Complexity.
Relevant reading: Kushilevitz/Nisan Chapter 2.1-2.4

Lecture 3: A Crash Course on Probability Theory, more on Nondeterministic Communication Complexity.
also Yao's Minimax Lemma, Newman's Theorem.
Relevant reading: A Computational Introduction To Number Theory and Algebra (CINTA) chapter 8, Kushilevitz/Nisan Chapter 2.5, 3.1-3.4

Lecture 4: Randomized Communcation Complexity
Relevant reading: Kushilevitz/Nisan Chapter 3.1-3.3

Lecture 5: Distributional CC, Discrepancy, the INNER PRODUCT function.
Relevant reading: Kushilevitz/Nisan Chapter 3.4, 3.5,

Lecture 6: A crash course on Information Theory
Relevant reading: BBCR-direct-sum paper

Lecture 7: More Infomation Theory, the INDEX lower bound, Circuit Complexity I
Relevant reading: Kushilevitz/Nisan 5, 10, BBCR-direct sum paper

Lecture 8: Circuit Complexity II
Karchmer-Wigderson Game, NOF complexity and connection to ACC
Relevant reading: Kushilevitz/Nisan 5, 10

Lecture 9: Data Structure lower bounds
Cell Probe model, asymmetric communication complexity

Lecture 10: Data Structure lower bounds

Lecture 11: Data Structure lower bounds
Lopsided Set Disjointness

Lecture 12: Data Structure lower bounds
Dynamic Data Structures, relation to NOF complexity, slack

Lecture 13: Streaming Algorithms
Alon-Matias-Szegedy, Gap-Hamming-Distance
Relevant reading: Alon-Matias-Szegedy paper, BCRVW-Gap-Hamming paper

Lecture 14: lower bounds for Property Testing, Conclusion
Relevant reading: BBM paper