6.896 Sublinear Time Algorithms
- Instructors:
Ronitt Rubinfeld and
Eli Ben- Sasson
- Time: TR 1:00-2:30
- Place: 36-156
- 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.
(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 triangle-free property: Szemeredi's Regularity
Lemma, and finding triangles in regular tri-partite graphs.
- 10/7:
Finish tester
for triangle-free property. Start lower bound
in terms of epsilon.
- 10/12:
Finish lower bound for triangle-free property.
- 10/14:
Max-cut.
- 10/19:
Finish max-cut. 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 error-correcting 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.