6.889 Sublinear Time Algorithms
 Instructor:
Ronitt Rubinfeld
 Time: MW 1:002:30
 Place: 34301
 309 HLevel 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

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

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

(02/13) Lecture 3:
Approximating the average degree in a graph in sublinear time.
[scanned notes]
[scribe notes]
[latex file for scribe notes]

(02/19) Lecture 4:
Using local distributed algorithms to design sublinear time
algorithms: the case of Vertex Cover.
[scanned notes]
[scribe notes]
[latex file for scribe notes]

(02/20) Lecture 5:
Using greedy algorithms to design sublinear time algorithms:
the case of Maximal Matching.
Begin Property testing: Testing planarity. Partition oracles.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(02/25) Lecture 6:
Testing planarity. Partition oracles.
[scanned notes]
[scribe notes]
[latex file for scribe notes]

(02/27) Lecture 7:
Testing bipartiteness in dense graphs.
[scanned notes]
[scribe notes]
[latex file for scribe notes]

(03/4) Lecture 8:
Testing trianglefreeness in dense graphs
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(03/6) Lecture 9:
Lower bound on testing trianglefreeness  superpolynomial dependence on
epsilon is required!
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(03/11) Lecture 10:
Lower bounds based on Yao's method.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(03/13) Lecture 11:
Testing Monotonicity.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(3/18) Lecture 12:
Property testing of distributions. Testing uniformity.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

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

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

(04/3) Lecture 15:
Monotonicity testing
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(04/5) Lecture 16:
Hypothesis testing.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

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

(04/25) Lecture 18:
Local computation algorithms for maximal independent set.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(05/2) Lecture 19:
Local computation algorithms for spanners
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(05/4) Lecture 20:
More on lower bound techniques: Lower bounds from communication complexity.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(05/9) Lecture 21:
Lower bounds for distribution testing: Communication
Complexity, Collisions.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(05/16) Lecture 22:
Linearity testing.
[scanned notes]
[scribe notes ]
[latex file for scribe notes]

(05/16 and 05/18) Lecture 23 and 24:
Probabilistically checkable proof systems.
[scanned 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 Feb 1, 2019.

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
Last modified March 14, 2019.

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
Last modified April 17, 2019.

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
Last modified 10:30pm April 11, 2019.

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
Last modified April 29, 2019.

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: