6.889 Sublinear Time Algorithms

Instructor: Prof. Ronitt Rubinfeld
Course admin: Joanne Hanley (joanne at csail.mit.edu)
Time: TTH 1:00-2:30 EST
Place: Zoom (see LMOD site under "information" for meeting ID, or write to Joanne Hanley at the email address given above).
3-0-9 H-Level Grad Credit
LMOD site contains zoom meeting ID and links to recordings of lectures..
Piazza site (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.

Announcements

  • Sign up for project presentation slots
  • Homework 4 is out!
  • Project information
  • Office hours: Thursday 5-6pm or by appointment.

    • Lecture Notes

    Note that links to lecture recordings are all on LMOD site.
    1. (9/1) Lecture 1: Overview. Diameter of a point set. Approximating the number of connected components. [slides] [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes]
    2. (9/3) Lecture 2: Approximating Minimum Spanning Tree in sublinear time. Begin approximating the average degree in sublinear time. [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes]
    3. (9/8) Lecture 3: Approximating the average degree of a graph. [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes] [latex file for scribe notes]
    4. (9/10) Lecture 4: Distributed Algorithms vs Sublinear time Algorithms: The case of Vertex Cover [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes] [latex file for scribe notes]
    5. (9/15) Lecture 5: Greedy algorithms vs Sublinear Time: the case of Maximal Matching. Property testing: is the graph planar? [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    6. (9/17) Lecture 6: Property testing: is the graph planar? [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes]
    7. (9/22) Lecture 7: Part I: Property testing: is the graph planar? [Handwritten notes (before class)] [Handwritten notes (during class)] Part II: Testing dense graphs - bipartiteness [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    8. (9/24) Lecture 8: Testing dense graphs: is the graph bipartite? [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    9. (9/29) Lecture 9: Szemeredi's Regularity Lemma. Testing dense graph properties via the SRL: triangle-freeness. [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    10. (10/1) Lecture 10: Testing dense graph properties via the SRL: triangle-freeness. Begin lower bound. [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    11. (10/6) Lecture 11: Testing triangle-freeness. The lower bound. [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    12. (10/8) Lecture 12: Testing distributions: the case of uniformity [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    13. (10/15) Lecture 13: Testing distributions: the case of uniformity (cont.) [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    14. (10/20) Lecture 14: More on Testing Distributions: Poissonization; Dealing with large L2-norm; Testing Closeness. [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    15. (10/22) Lecture 15: Learning and Testing Distributions: Monotonicity. [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    16. (10/27) Lecture 16: Hypothesis Testing [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    17. (10/29) Lecture 17: Testing monotonicity of functions [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    18. (11/3) Lecture 18: Lower bound techniques [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    19. (11/5) Lecture 19: Local computation Algorithms: Maximal Independent set [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    20. (11/10) Lecture 20: Matchings [Slobodan Mitrovic lecture notes] [scribe notes ] [latex file for scribe notes]
    21. (11/12) Lecture 21: Self-correcting for linear functions; testing linearity [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    22. (11/17) Lecture 22: Probabilistically Checkable Proof Systems [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    23. (11/19) Lecture 23: Probabilistically Checkable Proof Systems (continued) [Handwritten notes (before class)] [Handwritten notes (during class)] [scribe notes ] [latex file for scribe notes]
    24. (12/1) Lecture 24: Big Data (presented by Slobodan Mitrovic) [Slides] [scribe notes ] [latex file for scribe notes]
    25. (12/3) Lecture 25: Counting Edges and Sampling Edges (presented by Talya Eden) [Notes] [Notes] [scribe notes ] [latex file for scribe notes]

    Homeworks

    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, 2020.
    3. Problem set 1 Due September 15, 2020. Hint to problem 2.
      Solution to ps1, problem 1
      Solution to ps1, problem 2
      Solution to ps1, problem 3
    4. Problem set 2 Due September 29, 2020.
      Solution to ps2, problem 1
      Solution to ps2, problem 2
      Solution to ps2, problem 3
    5. Problem set 3 Due October 29, 2020.
      Solution to ps3, problem 1
      Solution to ps3, problem 2
      Solution to ps3, problem 3
    6. Problem set 4 Updated November 12. Due November 19, 2020.
      Solution to ps4, problem 1
      Solution to ps4, problem 2
    7. Problem set 5 (extra credit problems) Not due.

    Some useful pointers:

    Accessibility