Sublinear Time and Space Algorithms (semester 2020B)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures]
[Assignments] [Reading material]
Course description
Instructor: Robert
Krauthgamer
Grader: Ohad.Trabelsi (at weizmann.ac.il)
When and where: Mondays 14:15-16:00
14:00-15:45, taught via
Zoom Ziskind Lecture Room 1
First class: April 20, 2020
FGS code: 20204182
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 26 (via email), due within 72 hours. Its format
will be similar to previous years.
Here is the final assignment itself.
Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2020b-SublinearAlgorithms
Previous offerings:
http://www.wisdom.weizmann.ac.il/~robi/teaching/2018b-SublinearAlgorithms/
http://www.wisdom.weizmann.ac.il/~robi/teaching/2016b-SublinearAlgorithms/
Announcements
- [posted 2020-07-11]: Problem set 5 was corrected again (in
Q.#3,4, additive error is $\epsilon T$ instead of $\epsilon t$;
but k,k' changed back to original values)
- [posted 2020-07-10]: Problem set 5 was corrected ( in Q.#3,4,
the value of k and k' is changed)
- [posted 2020-06-22]: Final assignment schedule:
Distributed morning of July 26 (via email), due within 72 hours.
Its format will be similar to previous years.
- [posted 2020-05-18]: Starting next week, the class will start
at 14:00 instead of 14:15
Lectures
- 2020-04-20: Data-Stream Algorithms, Probabilistic Counting.
Reading: lecture notes #1. See also
Andoni,
lecture #1; Nelson,
lecture #1; Chekuri,
lecture #1.
- 2020-04-27: Reservoir Sampling, Frequency Vectors, Distinct
Elements, Frequency Moments and the AMS algorithm.
Reading: lecture notes #2. See also
Andoni,
lectures #2+3; Nelson,
lecture #2+3; Chekuri,
lecture #2+4.
Homework: problem set #1 below.
- 2020-05-04: Frequency Moments (l_2) and Point Queries (l_1).
Reading: lecture notes #3. See also
Andoni,
lectures #3+4; Nelson,
lecture #3+6; Chekuri,
lecture #4+6.
- 2020-05-11: Amplifying success probability, l_2 Point Queries,
and Hash Functions.
Reading: lecture notes #4. See also
Andoni,
lecture #3+4; Nelson,
lecture #2+6+7; Chekuri,
lecture #6.
- 2020-05-18: Hash Functions, Heavy Hitters, and Compressed
Sensing.
Reading: lecture notes #5. See also
Nelson,
lecture #2+6; Chekuri,
lecture #6+7.
Homework: problem set #2 below.
- 2020-05-25: Compressed Sensing, RIP matrices and Basis
Pursuit.
Reading: lecture notes #6. See also
Nelson,
lecture #19.
- 2020-06-01: Basis Pursuit and Iterative Hard Thresholding
Reading: lecture notes #7. See also
Nelson,
lecture #19+20.
- 2020-06-08: l_0-sampling and streaming of graphs.
Reading: lecture notes #8. See also
Andoni,
lecture #5; Nelson,
lecture #7.
Homework: problem set #3 below.
- 2020-06-15: Connectivity in dynamic graphs and triangle
counting
Reading: lecture notes #9. See also
Andoni,
lectures #5+6; Chakrabarti,
chapter #15.
- 2020-06-22: Geometric streams and coresets
Reading: lecture notes #10. See
also also Chakrabarti,
chapter #12; Beame,
lectures #13+14.
Homework: problem set #4 below.
- 2020-06-29: Sublinear-time algorithms for sparse graphs.
Reading: lecture notes #11. See
also survey
by Czumaj and Sohler.
- 2020-07-06: Sublinear-time algorithms for maximum matching and
vertex cover
Reading: lecture notes #12. See
also paper by
Hassidim, Kelner, Nguyen and Onak.
Homework: problem set #5 below.
- 2020-07-13: Sublinear-time algorithms for vertex cover and
communication complexity of equality
Reading: lecture notes #13; see
also Nelson,
lecture #9; Beame,
lecture #11
- 2020-07-20: Communication Complexity and Streaming Lower
Bounds
Reading: lecture notes #14; see
also Nelson,
lecture #9+10; Beame,
lectures #11+12.
Assignments
(Should usually be turned in within two weeks)
Reading material
Surveys and lecture notes:
Similar/related courses (many with lecture notes):
Useful references:
Other: