6.889 Sublinear Time Algorithms

Instructors: Ronitt Rubinfeld
Time: TR 11:00-12:30
Place: 24-115
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

  • Due date for projects: Last week of class project presentations. Short writeup due two days after the presentation. Speak to me if this is an issue. Sign up for a slot in the grading schedule document below!
  • Homework 9 is out!
  • revision to announcement in the next bullet -- I have only assigned 7 problems in total over psets 6-9. You only need to do 5 of them. If you have already done 6, please let me know, I will give extra credit.
  • Announcement made before HW 6 was put out: I will assign at least 8 more problems (over 4 psets -- 6,7,8,9) until the end of the semester. You only need to do 6 of them (you can pick which ones).
  • Please come see me about possible project ideas.

    • Lecture Notes

    1. (02/07) Lecture 1: Overview. Diameter of a point set. Approximating the number of connected components. Approximate Minimum Spanning Tree. [scanned notes] [scribe notes] [latex file for scribe notes]
    2. (02/14) Lecture 2: Approximating the average degree in sub-linear time. [scanned notes] [scribe notes draft] [latex file for scribe notes draft]
    3. (02/16) Lecture 3: Finish approximating the average degree (see notes from last time). Approximating vertex cover in sub-linear time via local distributed algorithms. [scanned notes] [scribe notes] [latex file for scribe notes]
    4. (02/23) Lecture 4: Continue approximating vertex cover in sub-linear time via local distributed algorithms. Approximating maximal matching via simulating greedy algorithms. [scanned notes] [scribe notes] (draft) [latex file for scribe notes]
    5. (02/28) Lecture 5: Property testing. Testing planarity. Partition oracles. [scanned notes] [scribe notes ] [latex file for scribe notes]
    6. (03/2) Lecture 6: Property testing of distributions. Testing uniformity. [scanned notes] [scribe notes] [latex file for scribe notes]
    7. (03/7) Lecture 7: Property testing of distributions. More on uniformity. [scanned notes -- same as lecture 6] [scribe notes] [latex file for scribe notes]
    8. (03/9) Lecture 8: Property testing of distributions. Lower bound techniques: Collisions, Information theory, Poissonization. [scanned notes] [scribe notes ] [latex file for scribe notes]
    9. (03/16) Lecture 9: Property testing of distributions. Testing closeness of two unknown distributions. Testing and learning monotone distributions. [scanned notes] [scribe notes ] [latex file for scribe notes]
    10. (03/21) Lecture 10: Testing and learning monotone distributions. [scanned notes] [scribe notes ] [latex file for scribe notes]
    11. (03/21) Lecture 11: Hypothesis testing. [scanned notes] [scribe notes ] [latex file for scribe notes]
    12. (04/4) Lecture 12: Learning and and testing PBDs. [scanned notes] [scribe notes ] [latex file for scribe notes]
    13. (04/6) Lecture 13: Testing Monotonicity. [scanned notes] [scribe notes ] [latex file for scribe notes]
    14. (04/11) Lecture 14: Testing Monotonicity under L1 distance. Begin testing properties of dense graphs (bipartiteness). [scanned notes] [scribe notes ] [latex file for scribe notes]
    15. (04/13) Lecture 15: Testing bipartiteness of dense graphs. [scanned notes] [scribe notes ] [latex file for scribe notes]
    16. (04/20) Lecture 16: Local computation algorithms for maximal independent set (guest lecture by Anak Yodpinyanee!). [notes] [scribe notes ] [latex file for scribe notes]
    17. (04/25) Lecture 17: The Szemeredi regularity lemma -- begin use in property testing of dense graphs. [scanned notes] [scribe notes ] [latex file for scribe notes]
    18. (04/25) Lecture 18: Using the Szemeredi regularity lemma for testing triangle-freeness. (see notes from lecture 17)
    19. (05/2) Lecture 19: Lower bounds from communication complexity. [scanned notes] [scribe notes ] [latex file for scribe notes]
    20. (05/4) Lecture 20: Lower bounds based on Yao's method. [scanned notes] [scribe notes ] [latex file for scribe notes]
    21. (05/9) Lecture 21: Lower bounds based arithmetic number theory. [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]

    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 3, 2017.
    3. Problem set 1 Due Feb 23, 2017 (note new deadline!).
      4. Last modified Feb 20, 2017.
    4. Problem set 2 Due March 2, 2017.
      5. Last modified Feb 23, 2017.
    5. Problem set 3 Due March 9, 2017.
      6. Last modified March 4, 2017.
    6. Problem set 4 Due March 21, 2017. (This overrides the due date written in the file).
      7. Last modified March 9, 2017.
    7. Problem set 5 Due April 6, 2017.
      8. Last modified March 22, 2017.
    8. Problem set 6 Due April 13, 2017.
      9. Last modified April 6, 2017.
    9. Problem set 7 Due April 20, 2017.
      10. Last modified April 6, 2017.
    10. Problem set 8 NOW DUE May 2, 2017.
      11. Last modified April 25, 2017.
    11. Problem set 9 Due May 9, 2017.
      12. Last modified May 2, 2017.

    Some useful pointers: