Sublinear Time and Space Algorithms (semester 2016B)

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

Course description

Instructor: Robert Krauthgamer 

Grader: Nimrod Talmon

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

First class: March 13, 2016

FGS code: 20164012

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.

Exam (final assignment): Here is the final assignment itself.

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

Announcements

• [posted 2016-05-31] problem set 4 was slightly corrected (in Q.#3)
  
• [posted 2016-05-29] final assignment schedule: distributed on June 28, and due within 5 days
  
• [posted 2016-05-15] no class on June 5 and 19
  
• [posted 2016-04-03] problem set 1 was slightly corrected
  
• [posted 2016-04-03] no class April 10, 17 and 24.
  
• [posted 2016-03-21] class of April 3 will take place in room 261
  
• [posted 2016-03-13] no class on 2016-03-20
  
• [posted 2016-03-13] most future classes will be extended till 13:00 

Lectures

1. 2016-03-13: data-stream algorithms, probabilistic counting, reservoir sampling, frequency vectors
   [reading: lecture notes #1; see also Andoni, lecture #1; Nelson, lecture #1; Chekuri, lecture #1]
   2016-03-20: no class
2. 2016-03-27: distinct elements, point queries and hash functions
   [reading: lecture notes #2; see also Andoni, lectures #2+3; Nelson, lecture #2+6; Chekuri, lecture #2+6]
   [homework: problem set #1 below]
3. 2016-04-03: l_2 frequency moment and point queries, heavy hitters, and compressed sensing
   [reading: lecture notes #3; see also Andoni, lectures #3+4; Nelson, lecture #3+6+7; Chekuri, lecture #4+6]
   2016-04-10: no class (faculty retreat)
   2016-04-17: no class
   2016-04-24: no class (Passover)
4. 2016-05-01: precision Sampling and high frequency moments
   [reading: lecture notes #4; see also Andoni, lectures #4+5; Nelson, lecture #4+5]
5. 2016-05-08: l_0-sampling and connectivity in dynamic graphs
   [reading: lecture notes #5; see also Andoni, lectures #6+7; Nelson, lecture #7]
   [homework: problem set #2 below]
6. 2016-05-15: triangle counting, geometric streams and coresets
   [reading: lecture notes #6; see also Andoni, lectures #6; Chakrabarti, chapter #12+15; Beame, lectures #13+14]
7. 2016-05-22: Sublinear-Time Algorithms for Sparse Graphs
   [reading: lecture notes #7; see also survey by Czumaj and Sohler]
   [homework: problem set #3 below]
8. 2016-05-29: Lower Bounds via Communication Complexity
   [reading: lecture notes #8; see also Nelson, lecture #9; Beame, lectures #12]
   [homework: problem set #4 below]
   2016-06-05: no class
   2016-06-12: no class (Shavout)
   2016-06-19: no class
9. 2016-06-26: More Lower Bounds and Algorithms for Sequences
   [reading: lecture notes #9; see also Nelson, lectures #10+8]

Assignments

• problem set 1 (posted March 28, corrected April 3)
  
• problem set 2 (posted May 9)
• problem set 3 (posted May 23), link to relevant paper, and a local copy (available inside Weizmann))
  
• problem set 4 (posted May 29, corrected May 31)

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