Fall, 2012

** Students should consult this page at least once a week
for important information. **

** **Posted Sept 2** See link below for choosing your topic for a research presentation. Your topic choice is due by Sept 30. Also class is cancelled next week, Sept 26th. **

** **Posted Oct 2** Homework 1 is posted below. It is due on Oct 31st at the start of class. **

** **Posted Nov 10** Homework 2 is posted below. It is due at the start of class on Nov 28. **

** Lectures: ** Wednesday 1-3 BA 2135

** Instructor: ** Toniann Pitassi

Office: Sandford Fleming 2305A, 978-3695

Office Hours: by appointment

** Tentative Course Outline (each week) **

** HOMEWORK **

** RESEARCH PRESENTATION **

** LINKS TO BOOKS, BOOK CHAPTERS, LECTURE NOTES
**

- Excellent new book by Lee and Shraibman
- Arora and Barak Book Chapter on Communication Complexity
- Raz's IAS Lectures on Communcication Complexity, (1)
- Raz's IAS Lectures on Communication Complexitiy (2)
- Raz's IAS Lectures on Communication Complexity (3)
- Raz's IAS Lectures on Communication Complexity (4)
- Raz's IAS Lectures on Communication Complexity (5)

** LINKS TO PAPERS
**

** COURSE LECTURE NOTES
**

**
***WARNING*** THESE ARE ROUGH DRAFTS AND ARE LIKELY TO CONTAIN ERRORS
**

Deterministic, probabilistic, nondeterministic communication complexity. Newman's theorem (private versus public coins), Important functions (equality, set disjointness)

Deterministic Lower Bounds: (1) rectangles; (2) fooling set argument; (3) rank lower bound method; Covers

Randomized Lower Bounds: Distributional Complexity and Yao's theorem, Discrepancy

Discrepancy method continued, Sherstov Dual Polynomial Method

Applications of Communication Complexity; Jain-Klauck: Communication Complexity Lower Bounds via LPs

For the first part of the lecture we will use the following paper: The Story of Set Disjointness

Dynamic Data Structures and Communication Complexity (Sandro Feuz)

The Clique-Independent Set Problem in Communication Complexity (Mike Goos)

Introduction to Information Complexity and Message Compression (Lila Fontes)

Zero Error Protocols and Message Compression (Lila Fontes)

Information Complexity Lower Bounds (Sergey Gorbunov)

Property Testing and Communication Complexity (Venkatesh Medabalimi)

Approximate Privacy (Lila Fontes) NOTE: These are slides, not lecture notes.

Differential Privacy in the Multiparty Setting (Yu Wu and Wesley George)