# CPSC 768

Scalable and Private Graph Algorithms

Instructor email: quanquan AT mit DOT edu

Instructor email: quanquan AT mit DOT edu

### Course Info

**Instructor:** Quanquan Liu

**Meeting times:** MW 11:30am - 12:50pm

### Course Description:

NEW: Open problem session survey: survey.What techniques can we use to deal with modern real-world data with billions of data points? How do we account for strong adversaries that violate the privacy of users providing this data? This course will provide you with the knowledge to tackle research questions in these domains. We will propose answers and techniques to these broad questions from an algorithmic standpoint, presenting foundational topics such as:

- The
**parallel, distributed, and streaming models**and algorithmic techniques commonly used within these models **Differential privacy**and mechanisms for private data analysis**Implementation techniques, tools, and examples**that demonstrate the practicality of these algorithms in real-world systems

**open problem sections**where we discuss (known) practice and research questions related to the topics in this course in a collaborative group setting.

### Tentative Schedule and Notes/Presentations

This is a very rough plan of the topics covered in this course; subject to (and likely will) change, specifically, student presentations can be shifted to other lecture dates by request.- Jan 17: Overview of Class and Logistics; Introduction to Parallel, Distributed, Streaming, and Privacy Models; Median Trick [Slides (Open Problem Session Survey)]
- Jan 19 (Monday Schedule): Median Trick (continued) [Lecture 1 and 2 Notes]
- Jan 22: Local Sublinear/Parallel/Distributed Graph Algorithms [Lecture 3 Notes][PowerPoint]
- Jan 24: Local Sublinear/Parallel/Distributed Graph Algorithms [Lecture 4]
- Jan 29: Sublinear Average Degree [Lecture 5][PowerPoint]
- Jan 31: Streaming Maximum Matching [Lecture 6][PowerPoint]
- Feb 5: Streaming Maximum Matching [see Lecture 6 notes]
- Feb 7: Streaming Maximum Matching[Lecture 8]
- Feb 12: Introduction to Differential Privacy [Lecture 9 and 10]
- Feb 14: Private Graph Algorithms: Part 1 [See Lecture 9 notes]
- Feb 19: Private Graph Algorithms: Part 2 [Lecture 11 and 12]
- Feb 21: Learning-Augmented Graph Algorithms
- Feb 26: Implementing Graph Algorithms in the Real World
- Feb 29, Mar 4, 6, 25, 27, April 1, 3, 8, 10: Student Presentations
- Apr 15, 17, 22, 24: Final Project Presentations