Sublinear Time and Space Algorithms (semester 2018B)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures]
[Assignments] [Reading material]
Course description
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/
Announcements
- [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 schedule: distributed on July
15 (by noon), due within 4 days.
- [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).
Lectures
- 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.
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: