6.5240 Sublinear Time Algorithms

Instructor: Prof. Ronitt Rubinfeld
Teaching Assistants: Sijin Peng (sijinp at mit dot edu)
Course admin: Joanne Hanley (joanne at csail dot mit dot edu)
Time: TR 2:30-4:00
Place: 36-153
Piazza site (see course canvas for access code) (Please note that anonymous postings are not anonymous to instructors).
Brief Course description: This course will focus on the design of algorithms that are restricted to run in sublinear time, and thus can view only a very small portion of the data. The study of sublinear time algorithms has been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the various techniques that have been applied to analyzing such algorithms. Topics include: Estimating parameters and properties of graphs (average degree, min vertex cover, MST, max matching, connected components, diameter, clusterability, bipartiteness); Sublinear time and local access to optimization solutions (coloring, maximal independent set); Estimating parameters and properties of distributions (entropy, support size, independence, uniformity, independence, monotonicity, is it a sum of independent variables?); Estimating properties of functions (linearity and low degree polynomial testing, monotonicity, linear threshold functions, number of relevant variables).

Course Requirements: Homework sets (25%). Midterm (25%). Project (25%). Scribe notes and class participation (25%). As part of class participation, students will be asked to help with grading of assignments and writing solution sets.

Prerequisites: 6.1220 (6.046) or equivalent.

Office hours:

Sijin's Office Hours: Mondays 5-6pm. 24-319.
Ronitt's Office hours: By appointment. Room 32-G698.

Announcements

  1. (9/22) We have updated problem 2 d) in pset 1: The target complexity allows polylog factors.
  2. (9/20) We have updated problem 2 b) and c) in pset 1: Every (1-epsilon) is replaced with (1-2epsilon).

Lecture Notes

  1. (9/10) Overview (slides). Diameter of a point set (slides). Estimating the average degree (handwritten notes). [slides] [handwritten notes] [scribe notes]
  2. (9/15) Some final words on estimating the average degree (handwritten notes from last time + slides). Estimating the number of connected components and the MST weight of a graph. [handwritten notes] [scribe notes]
  3. (9/17) Sublinear-time algorithm for coloring [handwritten notes] [scribe notes]
  4. (9/22) Finish coloring (handwritten notes from last time) [scribe notes]
  5. (9/24) Design sublinear algorithm from distributed algorithms [handwritten notes] [scribe notes]
  6. (9/29) Local Computation Algorithm: MIS [handwritten notes] [scribe notes]
  7. (10/1) Finish LCA for MIS (handwritten notes from last time)
  8. (10/6) Design sublinear algorithm from greedy algorithms [handwritten notes]

Homeworks

(Turn in on Gradescope) See project information for project due dates. Here is a LaTeX template that you can download if you like. You're not required to use it.
  1. If you are not familiar with Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about them (e.g., in a description given below in "useful pointers").
  2. Problem set 0 (Don't turn in. just for review.)
    3. Last modified September 10, 2026.
  3. Problem set 1 Due September 24, 2026, 10PM. Reference Solution
  4. Problem set 2 Due October 7, 2026, 10PM.

Some useful pointers:

Accessibility