# CPSC 768

Scalable and Private Graph Algorithms

Instructor email: quanquan DOT liu AT yale DOT edu

Instructor email: quanquan DOT liu AT yale 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: Private Graph Algorithms: Part 3 [See Lecture 11 notes]
- Feb 26: More Differential Privacy Mechanisms and Tools: Part 1 [Lecture 13 and 14]
- Feb 29: More Differential Privacy Mechanisms and Tools: Part 2 and MWU (start)
- March 4: Multiplicative Weight Updates: Part 1 [Lecture 15]
- March 6: Multiplicative Weight Updates: Part 2 [Lecture 16 and 17]
- March 25: Multiplicative Weight Updates: Part 3
- March 27: Multiplicative Weight Updates: Part 4 [Lecture 18]
- April 1: Differentially Private Laplacian Sparsification
- April 3: Dynamic Graph Algorithms [Lecture 20]
- April 8: Hitting Sets
- April 10: Parallel Graph Algorithms [Lecture 22]
- April 15: Algorithms Engineering: Theory in Practice [Lecture 23]
- April 17: Distributed Graph Algorithms [Lecture 24]
- April 22: Learning-Augmented Graph Algorithms [Lecture 25]
- April 24: Final Project Presentations