6.889 Sublinear Time Algorithms

Instructor:
Prof. Ronitt Rubinfeld
 Course admin: Joanne Hanley (joanne at csail.mit.edu)
 Time: TTH 1:002:30 EST
 Place: Zoom (see LMOD site under "information" for meeting ID, or write to
Joanne Hanley at the email address given above).
 309 HLevel 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 56pm or by appointment.
Lecture Notes
Note that links to lecture recordings are all on LMOD site.

(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]

(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]

(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]

(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]

(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]

(9/17) Lecture 6:
Property testing: is the graph planar?
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes]

(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]

(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/29) Lecture 9: Szemeredi's Regularity Lemma. Testing dense graph properties via the SRL: trianglefreeness.
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(10/1) Lecture 10: Testing dense graph properties via the SRL: trianglefreeness. Begin lower bound.
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(10/6) Lecture 11: Testing trianglefreeness. The lower bound.
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(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]

(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]

(10/20) Lecture 14: More on Testing Distributions: Poissonization; Dealing with large L2norm; Testing Closeness.
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(10/22) Lecture 15: Learning and Testing Distributions: Monotonicity.
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(10/27) Lecture 16: Hypothesis Testing
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(10/29) Lecture 17: Testing monotonicity of functions
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(11/3) Lecture 18: Lower bound techniques
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(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]

(11/10) Lecture 20: Matchings
[Slobodan Mitrovic lecture notes]
[scribe notes ]
[latex file for scribe notes]

(11/12) Lecture 21: Selfcorrecting for linear functions; testing linearity
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(11/17) Lecture 22: Probabilistically Checkable Proof Systems
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(11/19) Lecture 23: Probabilistically Checkable Proof Systems (continued)
[Handwritten notes (before class)]
[Handwritten notes (during class)]
[scribe notes ]
[latex file for scribe notes]

(12/1) Lecture 24: Big Data (presented by Slobodan Mitrovic)
[Slides]
[scribe notes ]
[latex file for scribe notes]

(12/3) Lecture 25: Counting Edges and Sampling Edges (presented by Talya Eden)
[Notes]
[Notes]
[scribe notes ]
[latex file for scribe notes]
Homeworks
 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").

Problem set 0 (Don't turn in. just for review.)
Last modified August 20, 2020.

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

Problem set 2
Due September 29, 2020.
Solution to ps2, problem 1
Solution to ps2, problem 2
Solution to ps2, problem 3

Problem set 3
Due October 29, 2020.
Solution to ps3, problem 1
Solution to ps3, problem 2
Solution to ps3, problem 3
 Problem set 4
Updated November 12.
Due November 19, 2020.
Solution to ps4, problem 1
Solution to ps4, problem 2

Problem set 5 (extra credit problems)
Not due.
Some useful pointers:
Accessibility