Sublinear Time and Space Algorithms (semester 2020B)

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

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

1. 2020-04-20: Data-Stream Algorithms, Probabilistic Counting.
   Reading: lecture notes #1. See also Andoni, lecture #1; Nelson, lecture #1; Chekuri, lecture #1.
2. 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.
   
3. 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.
4. 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.
5. 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.
6. 2020-05-25: Compressed Sensing, RIP matrices and Basis Pursuit.
   Reading: lecture notes #6. See also Nelson, lecture #19.
7. 2020-06-01: Basis Pursuit and Iterative Hard Thresholding
   Reading: lecture notes #7. See also Nelson, lecture #19+20.
8. 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.
9. 2020-06-15: Connectivity in dynamic graphs and triangle counting
   Reading: lecture notes #9. See also Andoni, lectures #5+6; Chakrabarti, chapter #15.
10. 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.
11. 2020-06-29: Sublinear-time algorithms for sparse graphs.
    Reading: lecture notes #11. See also survey by Czumaj and Sohler.
12. 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.
13. 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
14. 2020-07-20: Communication Complexity and Streaming Lower Bounds 
    Reading: lecture notes #14; see also Nelson, lecture #9+10; Beame, lectures #11+12.

Assignments

• problem set 1 (posted April 28)
  
• problem set 2 (posted May 18)
• problem set 3 (posted June 9)
• problem set 4 (posted June 22), link to relevant paper, and a local copy (available inside Weizmann) 
• problem set 5 (posted July 6)

Reading material

Surveys and lecture notes:

• 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)

Similar/related courses (many with lecture notes):

• 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)
  

Useful references:

• 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

Other:

• Open Problems in Sublinear Algorithms