Fall, 2014

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

POSTED SEPT 24: Topics for Presention listed below. Due date for picking a topic is Oct 3!

Nov 4 Game theory (Tyrone Strangeway and Jai Balasundaram);

Nov 11 Distributed Computing (Trevor Brown); Data Structures (Hao Wei);

Nov 18 Additive Combinatorics and Log Rank (Lalla Mouatadid); Property Testing (Nicolas Pena);

Nov 25 Information Complexity (Robert Robere).

** Lectures: ** Tuesdays 3-5 GB 248 (NOTE NEW ROOM!)

** Instructor: ** Toniann Pitassi

Office: Sandford Fleming 2305A, 978-3695

Office Hours: by appointment

** 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
**

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

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

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

- Lecture 4
Discrepancy method continued, Sherstov Dual Polynomial Method

- Lecture 5
Applications of Communication Complexity -- Monotone Circuit Depth

- Lecture 6
Monotone Circuit Depth Bounds via Set Disjointness, cont'd

- Lecture 7
Proof Complexity Lower Bounds via Set Disjointness

- Lecture 8
Extended Formulations and Communication Complexity

- Lecture 9
Game theory and Communication Complexity

- Lecture 10a
Distributed Computing and Communication Complexity

- Lecture 10b
Data Structures and Communication Complexity

- Lecture 11a
Additive Combinatorics

- Lecture 11b
Property Testing and Communication Complexity

- Lecture12
Information Complexity

- Sample scribe notes