Check
CS 7870 Seminar in Theoretical Computer Science (Spring 2026)
Course CS 7870 Seminar in Theoretical Computer Science: Algorithms for Big Data
Semester Spring 2026
Instructor Soheil Behnezhad (WVH 348)
Meeting Time Tuesdays 11:45am-1:25pm and Thursdays 2:50pm-4:30pm at Richards Hall 165
Office Hours Wednesdays 1pm (by appointment)
Prerequisites Mathematical maturity and some experience with probability and randomized algorithms. Students in areas other than theory are welcome to take the course!
Course Overview

The emergence of massive datasets has motivated a rapidly growing interest in algorithms that can process huge amounts of data. When working with such massive inputs, inherent assumptions of traditional algorithms (such as the possibility of reading or storing the whole input with a single machine) no longer hold. We thus need a new paradigm for the design and analysis of big data algorithms. This is precisely our focus in this course.

In this course, we focus on various algorithms whose time, space, or communication are much smaller than the input size. This includes sublinear time algorithms, streaming algorithms, distributed algorithms, massively parallel computation (MPC), among other topics.

Grading
This is a seminar and there will be no stress-inducing components such as quizzes and exams. Grades will be based on two lecture note scribes (30%), class participation (10%), and a reading/survey project, consisting of a mid-term proposal (10%), a final report (20%), and a final presentation (30%).

Schedule
# WD Date Topics Notes
Tu 1/13 Introduction and Models of Big Data Computation Lecture Notes
Th 1/15 Basic Probabilistic Tools Lecture Notes
Tu 1/20 Sublinear Time Algorithms: Connected Components & MST Lecture Notes
Th 1/22 Sublinear Time Algorithms: Connected Components & MST Lecture Notes
Tu 1/27 Sublinear Time Algorithms: Estimating Average Degree
Th 1/29 Sublinear Time Lower Bounds Lecture Notes
Tu 2/3 Sublinear Time Lower Bounds (Cont'd) Lecture Notes
Th 2/5 Sublinear Time Lower Bounds (Cont'd)
Tu 2/10 Streaming Algorithms: Distinct Elements
Th 2/12 Streaming Algorithms: Distinct Elements (cont'd)
Tu 2/17 Streaming Algorithms: Edge Coloring
Th 2/19 Streaming Algorithms: Edge Coloring (cont'd)
Tu 2/24 No Class: Winterstorm
Th 2/26 Graph Sparsification for Matching (Guest Lecture by Amir Azarmehr)
Tu 3/3 No Class: Spring Break
Th 3/5 No Class: Spring Break
Tu 3/10
Th 3/12
Tu 3/17
Th 3/19
Tu 3/24
Th 3/26 Midterm Proposals
Tu 3/31
Th 4/2 Final Project Presentations
Tu 4/7 Final Project Presentations
Th 4/9 Final Project Presentations
Tu 4/14 Final Project Presentations
Resources

There is no official textbook for the class and all required material will be available online. The following, however, is a list of helpful supplementary resources.