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-139.
Ronitt's Office hours: By appointment. Room 32-G698.
Announcements
Lecture Notes
-
(9/4) Overview (slides). Diameter of a point set (slides). Estimating
the average degree (handwritten notes).
[slides]
[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.
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