Fall, 2009

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

** ***Homework 2 is posted below...Due Nov 17*****

** Lectures: ** Tuesday 12-2 BA 3000 (Formerly BA 4010)

** Instructors: ** Toniann Pitassi
and Avner Magen

Office: Sandford Fleming 2305A, 978-3695

Office Hours: by appointment

**
HOMEWORK
**

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

- Communication Lower Bounds using Dual Polynomials, Sherstov
- The Pattern Matrix Method, Sherstov
- Sherstov CCC08 paper separating Product and Nonproduct Distributional Complexity
- Notes by Toniann Pitassi on Best Partition Communication Complexity
- Separation of the Monotone NC Hierarchy, Raz-Mckenzie
- Exponential Separation of Quantum and Classical Communication Complexity, Raz
- The BNS-Chung Criterion for Multiparty Communication Complexity

** SCRIBE NOTES
**

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