Sublinear Time and Space Algorithms (semester 2022B)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures]
[Assignments] [Reading material]
Grader: Shay.Sapir (at weizmann.ac.il)
When and where: Mondays 14:15-16:00, Ziskind Lecture Room
First class: March 28, 2022
FGS code: 20224092
Syllabus: The course will cover algorithms whose running
time and/or space requirement is sublinear in the input size. Such
algorithms can view only a small portion of the entire input, but
they are particularly suitable for analyzing massive data sets. In
recent years, this approach has been successfully used in several
areas, including graph theory, linear algebra, combinatorial
optimization, geometry, and string matching.
Prerequisites: Basic knowledge of algorithms, probability
and linear algebra at an undergraduate level.
Final: There will be a take-home exam. Distributed
morning of July 18 (via email), due within 72 hours. Its format
will be similar to previous years.
Here is the final assignment
- [posted 2022-06-07]: Final assignment schedule:
Distributed morning of July 18 (via email), and due within 72
hours. Its format will be similar to previous years.
- [posted 2022-05-07]: Problem set 2 was corrected (in Q#2, take
into the matrix A only the nonzero vectors)
- The class of 2022-05-02 is cancelled (recent FGS announcement
about Eid al-Fitr)
- 2022-03-28: Data-Stream Algorithms, Probabilistic Counting.
notes #1. See also Andoni,
lecture #1; Nelson,
lecture #1; Chekuri,
lecture #1; and paper by Nelson and Yu.
- 2022-04-04: Reservoir Sampling, Frequency Vectors, Distinct
notes #2. See also Andoni,
lectures #2; Nelson,
lecture #2; Chekuri,
Homework: problem set #1 below.
- 2022-04-11: Frequency Moments (l_2) and Point Queries (l_1).
notes #3. See also Andoni,
lectures #3+4; Nelson,
lecture #3+6; Chekuri,
- 2022-04-25: Amplifying success probability, l_2 Point Queries,
and Hash Functions.
notes #4. See also Andoni,
lecture #3+4; Nelson,
lecture #2+6+7; Chekuri,
Homework: problem set #2 below.
2022-05-02: no class (Eid al-Fitr)
- 2022-05-09: Adversarially Robust Streaming, Flip-Number and
notes #5. See also two papers by Ben-Eliezer,
Jayaram, Woodruff, and Yogev, and by Ben-Eliezer,
Eden, and Onak.
2022-05-16: no class (faculty retreat)
2022-05-23: no class
- 2022-05-30: Dynamic Geometric Streams and Euclidean MST.
notes #6. See also paper by Indyk.
- 2022-06-06: Euclidean MST (cont'd) and l_0-sampling
notes #7. See also Nelson,
Homework: problem set #3 below.
- 2022-06-13: Streaming of Graphs and Connectivity in Dynamic
notes #8. See also Andoni,
lecture #5+6; Nelson,
- 2022-06-20: Sublinear-time algorithms for sparse graphs.
notes #9. See also survey
by Czumaj and Sohler.
- 2022-06-27: Sublinear-time algorithms for maximum matching and
notes #10. See also paper by Hassidim,
Kelner, Nguyen and Onak.
Homework: problem set #4 below.
- 2022-07-04: Sublinear-time algorithms for vertex cover
- 2022-07-11: Communication Complexity and Streaming Lower
notes #12; see also Nelson,
lecture #9+10; Beame,
(Should usually be turned in within two weeks)
Surveys and lecture notes:
Similar/related courses (many with lecture notes):