Sublinear Time and Space Algorithms (semester 2016B)
Weizmann Institute of Science
[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
- 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
- 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]
- 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)
- 2016-05-01: precision Sampling and high frequency moments
[reading: lecture notes #4; see also
Andoni,
lectures #4+5; Nelson,
lecture #4+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]
- 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]
- 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]
- 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
- 2016-06-26: More Lower Bounds and Algorithms for Sequences
[reading: lecture notes #9; see also
Nelson,
lectures #10+8]
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: