ECS 289A: Sublinear Algorithms for Big Data
Winter 2026Instructor: Jasper Lee
Time: Tuesdays and Thursdays, 6:10pm-7:30pm
Location: Teaching and Learning Complex 1218
A huge quantity of data is worth little unless we can extract insights from it. Yet, the large quantities mean that classic algorithms (running in linear, quadratic or even more time) can be infeasible in practice. We must instead turn to new algorithmic approaches and paradigms, which allow us to answer valuable questions about our data in runtime that is still feasible even when the data set is Facebook-sized.
Surprisingly, to answer many computational and statistical questions, sometimes there is no need to read/store every piece of data! This course focuses on this exciting "sublinear" algorithmic regime.
See the course missive for details on assessment and various policies.
Piazza: Link (you might need to access it through Canvas for the first time)
This is an advanced graduate level course that is also suitable for strong undergraduate students.
Suggested prior preparation (see course missive above for details, and see Homework 0):
Mathematical maturity is essential: we will prove most of the results covered in the class. Almost all homework problems will require proof-writing. A student who cannot write clear precise proofs will almost certainly fail the course.