6.896 Sublinear Time Algorithms
 Instructors:
Ronitt Rubinfeld and
Eli Ben Sasson
 Time: TR 1:002:30
 Place: 36156
 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.
(Slightly more detailed
course announcement.)
Office hours: By appointment.
Announcements
Homework 3 has been posted below.
Handouts
Lecture Notes

09/9:
Introduction. Examples of deterministic sublinear time algorithms.
Example of a property tester.

09/14:
Definition of property tester, bounded degree graph testing model,
testing connectivity.

09/21:
Finishing off testing connectivity, estimating the number of
connected components.

09/23:
Estimating the minimum spanning tree weight.

09/28:
Bipartiteness testing.

09/30:
Finish proof of bipartiteness tester. Discussion
of tester for first order graph properties.
 10/5:
Tester for trianglefree property: Szemeredi's Regularity
Lemma, and finding triangles in regular tripartite graphs.
 10/7:
Finish tester
for trianglefree property. Start lower bound
in terms of epsilon.
 10/12:
Finish lower bound for trianglefree property.
 10/14:
Maxcut.
 10/19:
Finish maxcut. Start weak approximations of edit distance.
 10/21:
Weak approximations of edit distance (no scribe notes).
(Guest lecturer: Rahul Sami)
 10/26:
Finish weak approximations of edit distance (no scribe notes).
(Guest lecturer: Rahul Sami)
 10/28:
Clustering.
(Guest lecturer: Rahul Sami)
 11/2:
Matrix multiplication.
 11/4:
Lower bounds for testing low density parity check
codes and 3CNF formulas.
 11/9:
finish lower bound.
 11/16:
linearity testing.
 11/18:
preliminary draft.
 11/23:
Locally decodable errorcorrecting codes.
(Guest lecturer: Iordanis Kerenidis)
 11/30:
Monotonicity testing.
 12/2:
Proximity of distributions.
 12/7: Proximity of distributions. (no scribe notes)
 12/9: Testing uniformity of monotone distributions. (no scribe notes)
Homeworks
 If you are not familiar with
Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about
them in one or more of the descriptions given in useful pointers.

Homework 1 (Due October 7).
hint
Solution to problem 6.
Solution to problem 7.

Homework 2 (Due November 16).
(11/9) Note update to due date and to homework set.
Solution to problem 1.
Solution to problem 3.

Homework 3 (Due November 30).
Solutions .
Some useful pointers:
 References on Markov, Chebyshev and tail inequalities:

For future scribes, here is a
sample file and
the preamble.tex file that
it uses.

Instructions for graders.