- HW2 posted. Due on April 30.
- List of course projects posted here.
- HW1 posted. Due on Wednesday, February 15.
- First class on Wednesday, January 4.

- Class: W 10:00 am - 12:30 pm in ECE 1.07

- Homework 2
**(due on April 30)** - Homework 1
**(due on February 15)**

- Lecture 1: Tree protocols; deterministic, randomized, and distributional communication complexity; relation between randomized and distributional communication complexity
- Lecture 2: Random hashing for equality; 2-universal hash family; resolving a list of guesses; Slepian-Wolf theorem
- Lecture 3*: Leftover hash lemma (several versions); Function graph coloring and protocols for function computation
- Lecture 4: Simulating a zero-error 1-round protocol using Slepian-Wolf compression; improved simulation of 1-round protocols; amortized distributional complexity and information complexity
- Lecture 5*: Proof of lower bound for amortized distributional complexity; properties of interactive protocols; Application 1: Circuit complexity, circuit depth and the P vs NP question
- Lecture 6*: Karchmer-Widgerson duality for circuit depth and communication complexity of relations; lower bound for depth of circuit for finding a linear size matching;
- Lecture 7*: Lower bound for matching (contd.); reduction of matching to set-disjointness. Application 2: Streaming algorithms; Misra-Gries sketch; reduction of majority to index and the lower bound for storage required for 1-pass computation of majority.
- Lecture 8*: Lower bounds for deterministic communication complexity: Fooling set, rectangle size, rank lower bound; bounds among various measures of communication complexity: Randomized vs. deterministic, simple vs. interactive, private vs. public coins, boosting probability of correctness
- Lecture 9*: Rectangle lower bound for distributional communication complexity; Razborov's lower bound for randomized communication complexity of set-disjointness
- Lecture 10*: Partition bound and its relation to other bounds; Information complexity approach; Information complexity based lower bound for set-disjointness
- Lecture 11*: Holenstein's consistent sampling; Braverman-Rao sampling with communication
- Lecture 12*: BBCR direct-sum theorem using Information complexity; introduction to parallel repetition lemma
- Coming up ...

Holenstein's proof of parallel repetition lemma; Lifting query complexity bounds to communication complexity (Gòòz-Pitassi-Watson approach); Communication complexity of distributed inference.

- Deterministic communication complexity; Randomized communication complexity
- Distributional communication complexity; Yao’s minimax theorem
- Interactive data compression and function computation
- Variable partition model: Computation over networks and Complexity of implementing VLSI circuits
- Set disjointness: Space complexity of streaming algorithms
- Communication complexity of relations: Circuit complexity
- Lower bounds for deterministic communication complexity
- Reduction based lower bounds
- Partition lower bound
- Information complexity based lower bounds

- E. Kushilevitz and N. Nisan,
*Communication Complexity,*Cambridge University Press, 1997. - We will draw most of the material from research papers and online lecture notes.

Homework (2-4) | 60% |

Literature review (to be done in groups of size 2) | 30% |

Class Participation | 10% |