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