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
-
(11/2) We have noticed that the current statement for pset4 problem2 is confusing. We will make the following modifications to the statement: 1. You only need to prove the statement for every positive even number d; 2. In the two distributions, every graph should have an average degree in the interval [d-1, d], rather than exactly d. Due to the change, we will extend the pset deadline by two days.
-
(10/25) Practice midterm from Fall24: [Fall24 Midterm] [Fall24 Midterm (with Solution)]
-
(10/21)
Just to remind you that there is a project component to this course. You are allowed to team up
with one or two other students in the course, or to do the project on your own. There is general
information and some ideas for topics on a page pointed to from the course website. Please talk
to us about your plans early on, so that we can help you in finding a good topic. That same website
lists a due date of November 10 for you project proposal. That particular date is flexible, but do
come talk to us before that date. There are no requirements on length for the project proposal, it's
more to make sure that you are finding an interesting direction.
-
(10/21)
Regarding the midterm, here is the pertinent information:
Time: Wednesday 11/4 7:30-9 PM
Place: 32-124
Closed book, no cheat sheet. Necessary inequalities (like Chernoff bounds) and basic theorems will be provided in the exam.
Class on Thursday 11/5 is canceled.
-
(9/22) We have updated problem 2 d) in pset 1: The target complexity allows polylog factors.
-
(9/20) We have updated problem 2 b) and c) in pset 1: Every (1-epsilon) is replaced with (1-2epsilon).
Lecture Notes
-
(9/10) Overview (slides). Diameter of a point set (slides). Estimating
the average degree (handwritten notes).
[slides]
[handwritten notes]
[scribe notes]
-
(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]
-
(9/17) Sublinear-time algorithm for coloring
[handwritten notes]
[scribe notes]
-
(9/22) Finish coloring (handwritten notes from last time)
[scribe notes]
-
(9/24) Design sublinear algorithm from distributed algorithms
[handwritten notes]
[scribe notes]
-
(9/29) Local Computation Algorithm: MIS
[handwritten notes]
[scribe notes]
-
(10/1) Finish LCA for MIS (handwritten notes from last time)
[scribe notes]
-
(10/6) Design sublinear algorithm from greedy algorithms
[handwritten notes]
[scribe notes]
-
(10/8) Property testing for planar graphs
[handwritten notes]
[scribe notes]
-
(10/15) Finish partition oracle (notes from last time); Property testing for monotonicity
[slide]
[scribe notes]
-
(10/20) Finish property testing for monotonicity; Testing via implicit learning (slides); Testing monotonicity under L1 distance (handwritten notes)
[slide]
[handwritten notes]
[scribe notes]
-
(10/22) (Lecture by Lilly) LCA For Spanner
[handwritten notes]
[scribe notes]
-
(10/27) (Lecture by Sijin) Lower Bound via Yao's Principle
[handwritten notes]
[scribe notes]
-
(10/29) Property Testing over Dense Graphs: Bipartiteness
[handwritten notes]
-
(11/3) Finish Property Testing over Dense Graphs: Bipartiteness (Handwritten notes from last time)
-
(11/10) Szemeredi's Regularity Lemma and Testing Triangle Freeness over Dense Graphs
[handwritten notes]
[scribe notes]
-
(11/12) Finish Testing Triangle Freeness over Dense Graphs (Handwritten nodes from last time); Lower bound for testing triangle freeness
[handwritten notes]
[scribe notes]
(11/17) Finish lower bound for testing triangle freeness (Handwritten nodes from last time); Testing distributions: uniformity
[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.
- 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").
-
Problem set 0 (Don't turn in. just for review.)
Last modified September 10, 2026.
-
Problem set 1 Due September 24, 2026, 10PM.
Reference Solution
-
Problem set 2 Due October 7, 2026, 10PM.
Reference Solution
-
Problem set 3 Due October 21, 2026, 10PM.
Reference Solution
-
Problem set 4 Due November 5, 2026, 10PM.
-
Problem set 5 Due November 18, 2026, 10PM.
Some useful pointers:
- Tentative schedule of assignments, midterm, and project
- References on Markov, Chebyshev and tail inequalities:
-
For scribes:
- For graders:
-
Project information
- Recommended texts:
Accessibility