6.5240 Sublinear Time Algorithms

Instructor: Prof. Ronitt Rubinfeld
Teaching Assistant: Shyan Akmal (naysh at mit dot edu)
Course admin: Joanne Hanley (joanne at csail dot mit dot edu)
Course email: 65240-fa22 at csail.mit.edu
Time: MW 11:00-12:30 EST
Place: 34-302
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 (min vertex cover, MST, average degree, max matching, connected components, diameter, clusterability, bipartiteness); 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 (35%). Scribe notes (25%). Project (25%). Class participation (15%). As part of class participation, students will be asked to help with grading of assignments and writing solution sets.

Prerequisites: 6.046 or equivalent.

Shyan's Office hours: Mondays 4:30pm-5:30pm in 26-210.

Ronitt's Office hours: by appointment.


Announcements

  1. Optional makeup class on Friday 12/9 at 2pm in room 2-142. Will be taped!


Lecture Notes

  1. (9/12) Overview (slides). Diameter of a point set. Estimating the number of connected components. [slides] [handwritten notes] [scribe notes]
  2. (9/14) Estimating MST weight. Estimating Average degree. [Handwritten notes] [scribe notes]
  3. (9/19) Estimating average degree. [Handwritten notes] [scribe notes]
  4. (9/21) Finish estimating average degree (see notes from last time). Distributed algorithms vs sublinear time algorithms: the case of vertex cover. [Handwritten notes] [scribe notes]
  5. (9/15) Greedy algorithms vs Sublinear Time: the case of Maximal Matching. Property testing: is the graph planar? [Handwritten notes (see pages 9-14 in pdf)] [scribe notes]
  6. (9/28) Property testing; Testing Planarity; Partition oracles. [Handwritten notes] [scribe notes]
  7. (10/3) Finish planarity testing (see notes from last lecture). Begin property testing of dense graphs: is the graph bipartite? [Handwritten notes]> [scribe notes ]
  8. (10/5) Testing dense graphs: is the graph bipartite? (see notes from last time). If time: Begin testing triangle-freeness. [Handwritten notes] [scribe notes ]
  9. (10/12) Szemeredi's Regularity Lemma. Testing dense graph properties via the SRL: triangle-freeness. [Handwritten notes, continued from last time] [scribe notes ]
  10. (10/17) Testing triangle freeness: a lower bound. [Handwritten notes] [scribe notes ]
  11. (10/19) Lower bounds via Yao's method. [Handwritten notes] [scribe notes ]
  12. (10/24) Testing distributions: the case of uniformity [Handwritten notes] [scribe notes ]
  13. (10/26) Testing distributions: Finish uniformity. Monotonicity. [Handwritten notes] [scribe notes ]
  14. (10/31) Finish Monotonicity (see notes from last time). [Handwritten notes] [scribe notes ]
  15. (11/2) Linearity testing (guest lecture: Shyan Akmal). [scribe notes ]
  16. (11/7) Hypothesis Testing. Begin local computation algorithms. [Handwritten notes] [scribe notes ]
  17. (11/9) Local computation algorithms. Maximal independent set. [Slides] [Handwritten notes] [scribe notes]
  18. (11/14) Local computation algorithms. Finish maximal independent set. [Handwritten notes] [scribe notes ]
  19. (11/16) Local computation Algorithms: Spanners. [Handwritten notes] [scribe notes ]
  20. (11/21) Sublinear time coloring algorithms. [Handwritten notes] [scribe notes ]
  21. (11/28) Probabilistically checkable proof systems. [Handwritten notes] [scribe notes ]
  22. (11/30) Probabilistically checkable proof systems (cont.). [Handwritten notes (same as previous lecture)] [scribe notes]
  23. (12/5) Communication complexity lower bounds yield property testing lower bounds [Handwritten notes] [scribe notes]
  24. (12/7) Project Presentations
  25. (12/9) (optional makeup lecture) Monotonicity testing [slides] [scribe notes ]
  26. (12/12) Project Presentations
  27. (12/14) Local generation of huge random objects. [Slides]

Homeworks

(Turn in on Canvas) See project information for project due dates.
  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 20, 2022.
  4. Problem set 1 Due September 28, 2022. Hint to problem 2. Hint to problem 3.
  5. Problem set 2 Due October 12, 2022. Hint to problem 3.
  6. Problem set 3 Due October 26, 2022.
  7. Problem set 4 Due November 9, 2022.
  8. Problem set 5 Due November 30, 2022.
  9. Problem set 4 Due April 17, 2022.
    Solution to ps4, problem 1Latex version
    Solution to ps4, problem 3Latex version
    Solution to ps4, problem 4 Latex version
  10. Last modified April 29, 2019.
  11. Problem set 5 Due May 6, 2019. NOTE: In problem 1a, the runtime should be O(Delta) (not O(1)). (latex file also updated on 5/6)
    Solution to ps5, problem 1
    Solution to ps5, problem 2
    Solution to ps5, problem 3 Latex version -->

Some useful pointers:

Accessibility