[Course description] [Announcements] [Lectures] [Assignments] [Reading material]

**Instructor:** Robert
Krauthgamer

**Grader:** Shay.Sapir (at weizmann.ac.il)

**When and where:** Mondays 14:15-16:00, Ziskind Lecture Room
1

**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
itself.

**Webpage:** http://www.wisdom.weizmann.ac.il/~robi/teaching/2022b-SublinearAlgorithms

Previous offerings:

http://www.wisdom.weizmann.ac.il/~robi/teaching/2018b-SublinearAlgorithms/

http://www.wisdom.weizmann.ac.il/~robi/teaching/2016b-SublinearAlgorithms/

- [posted 2022-06-07]:
**Final assignment**

- [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.

Reading: lecture 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
Elements.

Reading: lecture notes #2. See also Andoni, lectures #2; Nelson, lecture #2; Chekuri, lecture #2.

Homework: problem set #1 below. - 2022-04-11: 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. - 2022-04-25: 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.

Homework: problem set #2 below.

2022-05-02: no class (Eid al-Fitr) - 2022-05-09: Adversarially Robust Streaming, Flip-Number and
Sparse-Dense Tradeoff.

Reading: lecture 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.

Reading: lecture notes #6. See also paper by Indyk.

- 2022-06-06: Euclidean MST (cont'd) and l_0-sampling

Reading: lecture notes #7. See also Nelson, lecture #7.

Homework: problem set #3 below. - 2022-06-13: Streaming of Graphs and Connectivity in Dynamic
Graphs.

Reading: lecture notes #8. See also Andoni, lecture #5+6; Nelson, lecture #7. - 2022-06-20: Sublinear-time algorithms for sparse graphs.

Reading: lecture notes #9. See also survey by Czumaj and Sohler. - 2022-06-27: Sublinear-time algorithms for maximum matching and
vertex cover

Reading: lecture 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

Reading: lecture notes #11. - 2022-07-11: Communication Complexity and Streaming Lower
Bounds

Reading: lecture notes #12; see also Nelson, lecture #9+10; Beame, lectures #11+12.

- problem set 1 (posted April 5)

- problem set 2 (posted April 26)
- problem
set 3 (posted June 7)

- problem set 4 (posted June 27)

- Small Summaries for Big Data by Cormode and Yi (2020)
- Data Stream Algorithms, lecture notes by Amit Chakrabarti (2020)
- Data Streams: Algorithms and Applications by S. Muthukrishnan (2005)
- Graph Stream Algorithms: a Survey by Andrew McGregor (2014)
- Sublinear-time algorithms by Artur Czumaj and Christian Sohler (2010)
- Sublinear Time Algorithms by Ronitt Rubinfeld (2006)
- Sketch Techniques for Approximate Query Processing by Graham Cormode (2011)
- The Continuous Distributed Monitoring Model by Graham Cormode (2013)
- Sketching as a Tool for Numerical Linear Algebra by David Woodruff (2014)

- Data Stream Algorithms by Amit Chakrabarti at Dartmouth (2020)
- Algorithms
for Big Data by Jelani Nelson at Harvard (2013)

- Algorithmic Techniques for Massive Data by Alexandr Andoni at Columbia (2015)
- Algorithms for Big Data by Chandra Chekuri at UIUC (2014)
- Sublinear Algorithms by Piotr Indyk and Ronitt Rubinfeld at MIT (2013)
- Sublinear and Streaming Algorithms by Paul Beame at U. of Washington (2014)
- Data Streams Algorithms by Andrew McGregor at UMass (2018)
- Introduction to Property Testing by Oded Goldreich at Weizmann (2015)
- Seminar
on Sublinear Time Algorithms by Ronitt Rubinfeld at Tel
Aviv U. (2016)

- Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi (errata)
- Concentration by Colin McDiarmid. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46