CPSC 768




Scalable and Private Graph Algorithms
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
This course focuses on advanced topics in practical graph algorithms with provable guarantees beyond the sequential model used in most introductory algorithms classes. Specific topics include local graph techniques for problems such as maximal matching, independent set, k-core decomposition, densest subgraphs, and coloring as well as global techniques for problems like connectivity, shortest paths, and spanners. Introductory lectures will also feature techniques used beyond graph algorithms. Students are asked to read and present influential recent research papers on these topics. Papers come from prominent CS theory conferences such as STOC, FOCS, SODA as well as database and data mining conferences like VLDB, PODS, and WWW. In addition to these presentations, students also work on a final project which may be theoretical or implementation-based. The course will also feature voluntary 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

Other Courses

A list of courses on subjects covered in this class.