Computer Science 49/149 (Fall 2014) |
 Computer Science Dartmouth College |
When: 2A hour, TTh 14:00-15:50, X-hr W 16:15-17:05
Where: Sudikoff 214
This course will introduce you to Communication Complexity, a subject that deals with how to perform a computation collaboratively when the input is not in one place but is split amongst two or more parties. The main objects of study will be communication protocols, which are efficient algorithms to solve such split-input problems. As computation has moved away from the basic isolated-computer setting to a complex, networked, cloud-enhanced setting, understanding the possibilities and limitations of such communication protocols has become increasingly important.
The course will first cover a number of key algorithms for basic communication problems. These algorithms will often feature a beautiful interplay between probability theory, graph theory, combinatorics, and algebra.
We will then move on to studying communication lower bounds, i.e., the limits of our ability to communicate efficiently. We will see that certain problems inhernetly require the parties holding the input to communicate very inefficiently, and we will understand in a mathematically precise way why this must be. This part of the course will use further probability theory, information theory, and linear algebra.
All advanced mathematical topics required for our study will be developed or reviewed within the course. The student is expected to have basic background in probability theory and linear algebra, and to be very comfortable writing mathematical proofs. Specific background in either Algorithms (CS 31) or the Theory of Computation (CS 39) is not an absolute requirement, but will be a plus.
An evolving class-by-class schedule is shown below. Specific mathematical background required for the topics covered in each class are shown after the '//' separator. The notation in brackets refers to sections of the textbook (see below) and/or to published papers that cover similar material.
Please be aware that we shall sometimes use the X-hour, even though the schedule table does not show this yet. Any such usage will be announced at least three days in advance.
| 1. | Sep 16 | Equality testing with fingerprints // basic probability, prime number theorem | [KN: 1.1, 3.1] | |
| 2. | Sep 18 | Algebraic fingerprints // finite fields, zeroes of polynomials | Homework 1 (due Sep 25) | |
| 3. | Sep 23 | Comparison and median-finding // binary search, Chernoff bounds | [KN: exercises] | |
| 4. | Sep 25 | Set intersection and disjointness | [KN: 3.3], [BCKWY] | Homework 2 (due Oct 2) |
| 5. | Sep 30 | Determinism, randomization, private-vs-public // the probabilistic method | [KN: 3.2, 3.3] | |
| 6. | Oct 2 | Simultaneous messages, amortization, economy-of-scale // codes | [BK], [FKNN] | Homework 3 (due Oct 9) |
| 7. | Oct 7 | Distributional complexity, minimax principle // zero-sum games, linear programming | [KN: 3.4] | |
| 8. | Oct 9 | One-way versus interactive protocols, rounds | [KN: 4.2] | Homework 4 (due Oct 16) |
| 9. | Oct 14 | (not used) | ||
| 10. | Oct 16 | (not used) | Homework 5 (due Oct 23) | |
| 11. | Oct 21 | Discrepancy, inner-product, disjointness // matrix rank, eigenvalues | [KN: 3.5] | |
| 12. | Oct 23 | Introduction to information theory | Homework 6 (due Oct 30) | |
| 13. | Oct 28 | More information theory; tight lower bound for augmented indexing | ||
| 14. | Oct 30 | Information complexity; disjointness revisited | ||
| 15. | Nov 4 | Information complexity of 1-bit AND // probability "metrics" | Homework 7 (due Nov 11) | |
| 16. | Nov 6 | Single-tape Turing Machines; Data Streaming | [KN: 12.2] | |
| 17. | Nov 11 | Lower bounds for Data Streaming and Data Strutures | [KN: 9.2] | Homework 8 (due Nov 18) |
| 18. | Nov 13 | Applications to circuits: Number-on-Forehead complexity | [KN: 6] | |
| 19. | Nov 18 | Applications to circuits: Karchmer-Wigderson games | [KN: 5.3,10.2,10.3] |
There is no set textbook for the course, so it is vital to attend class. However, much of the material we shall cover (and all of the introductory material) can be found in the following excellent textbook.
- Communication Complexity . Eyal Kushilevitz and Noam Nisan.
Here are notes covering certain topics that do not appear in the textbook.
Homework: There will be a short homework, consisting of 2-3 problems, given out every Thursday. It will be due the next Thursday, before class. The grading formula will be such that you have to turn in about 50%-60% of the homework. Collaboration on homework problems is allowed and encouraged, but please write your solutions entirely on your own, do not look at anyone else's final draft of solutions, and list all people you discussed/collaborated with.
Research Presentation: In lieu of a final exam, students will read, understand, and present (using slides) a paper chosen from a small list. Each paper will be presented by a team of two students, and the presentation should be 25-30 minutes long.
- Barak, Braverman, Chen, and Rao. "How to Compress Interactive Communication."
- Chattopadhyay, Radhakrishnan, and Rudra. "Topology Matters in Communication."
- Harsha, Jain, McAllester, and Radhakrishnan. "The Communication Complexity of Correlation."
- Huang and Yi. "The Communication Complexity of Distributed ε-Approximations."
- Jayram. "Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND."
- Phillips, Verbin, and Zhang. "Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy."
- Sherstov. "The Communication Complexity of Gap Hamming Distance."
Other courses taught by Amit Chakrabarti