Syllabus

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: 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

Other Courses

A list of courses on subjects covered in this class.