Below you'll find papers, surveys, and other documents relevant to the course.
Information on the oral exam.
- Use this include file to write your notes.
- This example shows how to use the include file.
- Our students developed a fine set of scribe notes for the class.
Exercises: Exercise sets are optional in this class, but
it's a good idea to work on them, as it will help you for the oral
- How To
Compress Interactive Communication. Boaz Barak, Mark
Braverman, Xi Chen, Anup Rao. STOC 2010.
- On Data
Structures and Asymmetric Communication Complexity. Peter Bro
Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson. STOC 1995.
Complexity and the Direct Sum Problem for Simultaneous Message
Complexity. Amit Chakrabarti, Yaoyun Shi, Anthony Wirth,
Andrew Yao. FOCS 2001.
- An Information Statistics Approach to Data Stream
and Communication Complexity. Ziv Bar-Yossef, T.S. Jayram,
Ravi Kumar, D. Sivakumar. FOCS 2002.
- Monotone Circuits for Connectivity Require
Super-Logarithmic Depth. Mauricio Karchmer, Avi Wigderson.
- Tighter Lower Bounds for Nearest Neighbor Search and
Related Problems in the Cell Probe Model. Omer Barkol, Yuval
Rabani. JCSS 2002.
- Towards Polynomial Lower Bounds for Dynamic
Problems. Mihai Patrascu. STOC 2010.
Space Complexity of Approximating Frequency Moments. Noga
Alon, Yossi Matias, Mario Szegedy. JCSS 1999.
Gap-Hamming Bounds via Better Round Elimination. Joshua
Brody, Amit Chakrabarti, Oded Regev, Thomas Viddick, Ronald de
Wolf. RANDOM 2010.
- Property Testing Lower Bounds
via Communication Complexity. Eric Blais, Joshua Brody, Kevin
Matulef. CCC 2011.