6.889 Sublinear Time Algorithms

Instructor: Ronitt Rubinfeld
Time: MW 1:00-2:30
Place: 34-301
3-0-9 H-Level Grad Credit
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.045 or 6.046 or equivalent.

Announcements

  • Project presentations in lecture last week of class. Sign up here. Slots are 8 minutes, please prepare no more than 5 minutes of presentation.
  • Project writeups due last week of class. Come see me for questions/advice/suggestions.

    • Lecture Notes

    1. (02/06) Lecture 1: Overview. Diameter of a point set. Approximating the number of connected components. [scanned notes] [scribe notes] [latex file for scribe notes]
    2. (02/11) Lecture 2: Approximating Minimum Spanning Tree in sublinear time. Begin approximating the average degree in sublinear time. [scanned notes] [scribe notes] [latex file for scribe notes]
    3. (02/13) Lecture 3: Approximating the average degree in a graph in sub-linear time. [scanned notes] [scribe notes] [latex file for scribe notes]
    4. (02/19) Lecture 4: Using local distributed algorithms to design sub-linear time algorithms: the case of Vertex Cover. [scanned notes] [scribe notes] [latex file for scribe notes]
    5. (02/20) Lecture 5: Using greedy algorithms to design sub-linear time algorithms: the case of Maximal Matching. Begin Property testing: Testing planarity. Partition oracles. [scanned notes] [scribe notes ] [latex file for scribe notes]
    6. (02/25) Lecture 6: Testing planarity. Partition oracles. [scanned notes] [scribe notes] [latex file for scribe notes]
    7. (02/27) Lecture 7: Testing bipartiteness in dense graphs. [scanned notes] [scribe notes] [latex file for scribe notes]
    8. (03/4) Lecture 8: Testing triangle-freeness in dense graphs [scanned notes] [scribe notes ] [latex file for scribe notes]
    9. (03/6) Lecture 9: Lower bound on testing triangle-freeness -- superpolynomial dependence on epsilon is required! [scanned notes] [scribe notes ] [latex file for scribe notes]
    10. (03/11) Lecture 10: Lower bounds based on Yao's method. [scanned notes] [scribe notes ] [latex file for scribe notes]
    11. (03/13) Lecture 11: Testing Monotonicity. [scanned notes] [scribe notes ] [latex file for scribe notes]
    12. (3/18) Lecture 12: Property testing of distributions. Testing uniformity. [scanned notes] [scribe notes ] [latex file for scribe notes]
    13. (03/20) Lecture 13: Property testing of distributions: Testing uniformity (cont.). Testing and learning monotone distributions. [scanned notes] [scribe notes ] [latex file for scribe notes]
    14. (04/1) Lecture 14: Poissonization. Flattening distributions. Testing closeness of two unknown distributions. (guest lecturer: Maryam Aliakbarpour) [scanned notes] [scribe notes ] [latex file for scribe notes]
    15. (04/3) Lecture 15: Monotonicity testing [scanned notes] [scribe notes ] [latex file for scribe notes]
    16. (04/5) Lecture 16: Hypothesis testing. [scanned notes] [scribe notes ] [latex file for scribe notes]
    17. (04/10) Lecture 17: Learning and and testing Poisson Binomial Distributions (PBDs). Local computation algorithms. [scanned notes on PBDs] [slides on LCAs] [scribe notes ] [latex file for scribe notes]
    18. (04/25) Lecture 18: Local computation algorithms for maximal independent set. [scanned notes] [scribe notes ] [latex file for scribe notes]
    19. (05/2) Lecture 19: Local computation algorithms for spanners [scanned notes] [scribe notes ] [latex file for scribe notes]
    20. (05/4) Lecture 20: More on lower bound techniques: Lower bounds from communication complexity. [scanned notes] [scribe notes ] [latex file for scribe notes]
    21. (05/9) Lecture 21: Lower bounds for distribution testing: Communication Complexity, Collisions. [scanned notes] [scribe notes ] [latex file for scribe notes]
    22. (05/16) Lecture 22: Linearity testing. [scanned notes] [scribe notes ] [latex file for scribe notes]
    23. (05/16 and 05/18) Lecture 23 and 24: Probabilistically checkable proof systems. [scanned 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 Feb 1, 2019.
    3. Problem set 1 (Note that lower bound problem was removed and one more problem was added)(Hint added 2/20) Due Feb 25, 2019.
      Solution to ps1, problem 1 Latex version
      Solution to ps1, problem 2 Latex version
      Solution to ps1, problem 3
      4. Last modified March 14, 2019.
    4. Problem set 2 (will add problems that are not to be turned in) Due March 18, 2019.
      Solution to ps2, problem 1
      Solution to ps2, problem 2
      Solution to ps2, problem 3
      5. Last modified April 17, 2019.
    5. Problem set 3 Due April 3, 2019.
      Solution to ps3, problem 1
      Solution to ps3, problem 2
      Solution to ps3, problem 3
      Solution to ps3, problem 4
      6. Last modified 10:30pm April 11, 2019.
    6. Problem set 4 Due April 17, 2019.
      Solution to ps4, problem 1Latex version
      Solution to ps4, problem 3Latex version
      Solution to ps4, problem 4 Latex version
      7. Last modified April 29, 2019.
    7. 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: