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

**Instructor:** Robert
Krauthgamer

**Grader:** Chen Attias

**When and where:** Sundays 10:15-12:00, Ziskind Lecture Room
1

**First class: **March 18, 2018

**FGS code:** 20184022

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

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

**
Final:** There will be a final assignment (take-home exam).
Here is the final assignment itself.

** Previous offerings:**

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

- [posted 2018-07-14] to get a copy of the
**final assignment**, email me by July 15 - [posted 2018-06-18] lecture notes #12 was expanded (added last
lemma and proof)

- [posted 2018-06-01] problem set 4 was slightly corrected (Q.
#1,2 are now specify explicitly the desired success probability)

- [posted 2018-05-28]
**final assignment**

- [posted 2018-04-19] problem set 2 was corrected (due date was
wrong)

- [posted 2018-03-18] for a quick idea about the topics of the
class, watch the 15-minute YouTube talk "Some
Important Streaming Algorithms You Should Know About" by Ted
Dunning (MapR).

- 2018-03-18: Data-stream algorithms, probabilistic counting,
reservoir sampling, frequency vectors.

Reading: lecture notes #1. See also Andoni, lecture #1; Nelson, lecture #1; Chekuri, lecture #1. - 2018-03-25: Distinct elements and point queries.

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

Homework: problem set #1 below.

2018-04-01: no class (Passover) - 2018-04-08: l_2 frequency moment and point queries.

Reading: lecture notes #3. See also Andoni, lectures #3+4; Nelson, lecture #3+6+7; Chekuri, lecture #4+6.

- 2018-04-15: Amplifying success and hash functions.

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

Homework: problem set #2 below. - 2018-04-22: Heavy hitters, compressed sensing, and range
queries.

Reading: lecture notes #5. See also Chekuri, lecture #6+7. - 2018-04-29: Compressed Sensing via RIP matrices and Basis
Pursuit.

Reading: lecture notes #6. See also Nelson, lecture #19. - 2018-05-06: Precision Sampling and High Frequency Moments
queries.

Reading: lecture notes #7. See also Andoni, lectures #4+5; Nelson, lecture #4+5.

Homework: problem set #3 below. - 2018-05-13: l_0-sampling and streaming of graphs.

Reading: lecture notes #8. See also Andoni, lecture #5; Nelson, lecture #7.

2018-05-20: no class (Shavuot) - 2018-05-27: Connectivity in dynamic graphs and triangle
counting

Reading: lecture notes #9. See also Andoni, lectures #5+6; Chakrabarti, chapter #15.

Homework: problem set #4 below. - 2018-06-03: Geometric streams and coresets

Reading: lecture notes #10. See also also Chakrabarti, chapter #12; Beame, lectures #13+14.

- 2018-06-10: Sublinear-time algorithms for sparse graphs .

Reading: lecture notes #11. See also survey by Czumaj and Sohler. - 2018-06-17: Sublinear-time algorithms for sparse graphs
(cont'd)

Reading: lecture notes #12. See also paper by Hassidim, Kelner, Nguyen and Onak.

- 2018-06-24: Lower bounds via communication complexity of
Indexing

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

Homework: problem set #5 below. - 2018-07-01: More streaming lower bounds

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

- problem set 1 (posted March 25)
- problem set 2 (posted April 15)
- problem set 3 (posted May 6)
- problem set 4 (posted May 28)
- problem set 5 (posted June 25)

- Data Stream Algorithms, lecture notes by Amit Chakrabarti (2015)
- 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 (2015)
- 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 (2012)
- 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