6.5240 Sublinear Time Algorithms

Instructor: Prof. Ronitt Rubinfeld
Teaching Assistants: Jane Lange (jlange at mit dot edu) and Matthew Hong (matthong at mit dot edu)
Course admin: Joanne Hanley (joanne at csail dot mit dot edu)
Time: MW 1:00-2:30
Place: 66-168
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:

Jane's office hours: 6pm-8pm Tuesdays in 26-314
Matt's Office hours: 5pm-6pm Mondays in 24-319
Ronitt's Office hours: By appointment and Mondays 2:30pm-3:30pm. Room 32-G698.

Announcements

Lecture Notes

  1. (9/4) Overview (slides). Diameter of a point set (slides). Estimating the average degree (handwritten notes). [slides] [handwritten notes] [scribe notes]
  2. (9/9) Estimating Average degree. [Handwritten notes] [scribe notes]
  3. (9/11) Estimating the number of connected components. Estimating MST. [Handwritten notes] [scribe notes]
  4. (9/16) Sublinear time coloring algorithms. [Handwritten notes] [scribe notes ]
  5. (9/18) Distributed algorithms vs sublinear time algorithms: the case of vertex cover. [Handwritten notes]
  6. (9/23) Greedy algorithms vs. sublinear time algorithms: the case of matching. Begin property testing for planar graphs. [Handwritten notes]
  7. (9/25) Property testing for planar graphs. [Handwritten notes] [scribe notes]
  8. (9/30) Finish planarity testing via partition oracles. (see notes from last time)
  9. (10/2) Local Computation Algorithms (LCA) model. LCA for Maximal Independent Set (begin). [Handwritten notes] [scribe notes]
  10. (10/7) LCA for Maximal Independent Set (continued). [Handwritten notes] [scribe notes]
  11. (10/9) Local computation Algorithms: Spanners. [Handwritten notes] [scribe notes]
  12. (10/16) Lower bounds via Yao's Method. [Handwritten notes]
  13. (10/21) Monotonicity Testing. [Handwritten notes]
  14. (10/23) Testing Distributions: Uniformity. [Handwritten notes] [scribe notes]
  15. (10/28) Testing closeness of two unknown distributions. [Handwritten notes]
  16. (10/30) Testing monotonicity of distributions. [Handwritten notes] [scribe notes]
  17. (11/4) Testing dense graphs -- the case of bipartiteness. [Handwritten notes]
  18. (11/6) Testing triangle-freeness in dense graphs. [Handwritten notes]
  19. (11/18) A lower bound for testing triangle-freeness. [Handwritten notes]
  20. (11/20) Testing and correcting linear functions [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 August 31, 2024.
  3. Problem set 1 Due September 18, 2024, 10PM.
  4. Problem set 2 Due October 2, 2022, 10PM. Hint to problem 2 Hint to problem 3
  5. Problem set 3 Due October 18, 2022, 10PM, extended due to student holidays. Hint to problem 1 Hint to problem 3 Hint to problem 4
  6. Problem set 4 Due October 30, 2022, 10PM.
  7. Problem set 5 Due November 20, 2022, 10PM. Hint to problem 2 Hint to problem 4(a)

Some useful pointers:

Accessibility