Information on the oral exam.

**Scribe Notes:**

- 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
exam.

- basic information
- homework 1
- homework 2
- homework 3
- homework 4
- homework 5
- homework 6
- homework 7
- homework 8
- homework 12
- homework 13
- homework 14

**Surveys:**

- Chapter 8 of A Computational Introduction to Number Theory and Algebra by Victor Shoup gives a good development of basic probability theory for computer scientists.

**Research Papers:**

- 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.
- Informational 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. STOC 1988.
- 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.
- The Space Complexity of Approximating Frequency Moments. Noga Alon, Yossi Matias, Mario Szegedy. JCSS 1999.
- Better 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.