Computer Science
Tel-Aviv University

0368.4612
Seminar on Sublinear Time Algorithms

Instructor: Ronitt Rubinfeld
Fall 2015

Course Description

With the growing importance of massive data sets, there has been increased interest in algorithms that consider only a very small portion of the data, in particular, algorithms which run in sublinear time. The study of sublinear time algorithms has been applied to problems from a wide range of areas, and many beautiful techniques have been applied to analyzing such algorithms, including the Szemeredi Regularity Lemma, low rank approximations of matrices, Fourier analysis, and other tools from number theory, combinatorics, linear algebra, optimization theory and probability theory. We will look at both classical and cutting edge papers in this area. Students are expected to read and present a paper or a small set of papers on a topic.

Grading

will be based on the student presentation of the papers and class participation.

Prerequisites

Some knowledge of algorithms and basics of probability.

Time and location

The seminar will take place on Sundays, 13:00-15:00, in room Orenshtein 110.

Announcements

List of Possible Topics

click here.

(Tentative) Schedule

sign up here

Date Topic Speaker
Oct 18 Introduction to course; Introduction to sublinear time Algorithms. Ronitt
Oct 25 Streaming algorithms (Introduction) Nitzan Weissman
Nov 1 Streaming algorithms for frequency cap statistics Inbar Shulman
Nov 8 Learning distributions Amit Osi
Nov 15 More streaming: Bloom filter and count-min sketch Amit Kol
Nov 22 Sublinear time pagerank Oded Elbaz
Nov 29 TBA TBA
Dec 6 no class enjoy!
Dec 13 Hanukah vacation enjoy!
Dec 20 Low degree testing and Local computation of pagerank contributions Danny V. and Omer Rotem
Dec 27 Testing expansion and Image matching Shay Gershtein and Shira G.
Jan 3 Local algorithms for sparse spanning graphs Nataly B.
Jan 17 TBA and TBA Guy Braude and Moab Arar.

Useful Pointers