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
Relevant reading: Alon-Matias-Szegedy paper, BCRVW-Gap-Hamming paper
Lecture 14: lower bounds for Property Testing, Conclusion
Relevant reading: BBM paper