Computer Science
Tel-Aviv University

Sublinear time algorithms

Instructor: Ronitt Rubinfeld
Fall 2009

Brief Course Description

This course will focus on the design of algorithms that are restricted to run in sublinear time, and thus can view only a very small portion of the data. The study of sublinear time algorithms has been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the various techniques that have been applied to analyzing such algorithms.


Will be based on the solutions to homework exercises and class participation. Undergraduates will also have a final exam.


Algorithms. Exposure to computational complexity is helpful but not required.

Time and location

The course will take place on Mondays, 13:00-16:00, in Physics-Shenkar 204.

Course Information Handout

More details on syllabus, grading, etc. (pdf) (see also "useful pointers" below)


Lecture notes

  1. October 19. Three examples of sublinear time algorithms: Diameter of a point set, monotonicity of a list, connectivity of a graph. (latex source)
  2. October 26. Estimating the number of connected components, minimum spanning tree. (latex source)
  3. November 2. Distributed computing vs. sublinear time: A reduction and a distributed algorithm. Approximating vertex cover and maximal matching in sublinear time. (latex source)
  4. November 9. Maximal matching. Approximating the average degree. (latex source)
  5. November 16. Property testing in dense graphs: bipartiteness. A canonical form for dense graph property testers.
  6. November 23. Property testing in dense graphs: tester for triangle-freeness. Use of Szemeredi's Regularity Lemma. (latex source)
  7. November 30. Property testing in dense graphs: any tester for triangle-freeness needs superpolynomial queries in epsilon. (latex source)
  8. December 7. Testing of clustering. Weak approximations of edit distance. (latex source)
  9. December 14. Testing boolean functions: Fourier analysis basics. Testing linearity.
  10. December 21. Testing boolean functions: Testing dictatorships. Begin testing juntas.
  11. December 28. Testing juntas.
  12. January 4. Testing properties of distributions: uniformity.
  13. January 11. Testing properties of distributions that are known to be monotone: uniformity.
  14. January 18. Streaming algorithms: estimating the L2 norm.


Useful Pointers