Topics in Algorithms – Sublinear Algorithms

0510.7410

 

Administrative Information.

Lectures: Mondays  4-6

Lecturer:   Dana Ron, danar at eng.tau.ac.il.

Office hours: Can be coordinated by email.

 

Brief Course Description: 
In the analysis of algorithms, the notion of efficiency is almost always assumed to mean polynomial time, where the gold standard of achievement is linear time. However, when the input is very large, even linear time may be prohibitive. This course will focus on the design and analysis of algorithms that are restricted to run in sublinear time, and thus can view only a very small portion of the input data. Such algorithms are, by nature, randomized approximation algorithms. As we shall see, despite the limitation to run in sublinear time (or even time that is independent of the input size), such algorithms exist

for a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. The course will introduce many of the various techniques  that have been applied to analyzing such algorithms.

 

 

Topics.
The course will include topics from the following list.

v     Dense graphs: Bipartitness, r-Clique, first order graphs properties
(using the regularity lemma).

v     Bounded-degree and sparse graphs: Connectivity, Diameter.

v     Directed graphs: Acyclicity.

 

Bibliography.
The course is based on several papers that have been published in the
last few years. The course web-site will include pointers to all these papers.
Most of these papers can be downloaded by clicking here.

 

Requirements.

Homework will be assigned about every two weeks.
Cooperation is allowed but each student must write his/her own solution.

There will be a final project that will involve reading, summarizing, and presenting

research papers on sublinear algorithms.

 

Handouts.

  1. Syllabus.
  2. Some probabilistic background.

 

 

Other Information

  1. Instructions for course mailing list.
  2. Messages sent on course mailing list.

 

Notes 
Disclaimer: these notes were not carefully proof-read (please let me know if you find typos/errors)

 

  1. Notes for lecture #1: Introduction
  2. Property testing of graphs: models and results in bounded degree graphs (part I).
  3. Testing k-connectivity and bipartiteness in bounded-degree/sparse graphs.
  4. Testing bipartiteness in dense graphs (from Design and Analysis of Algorithms course).
  5. Applying the regularity lemma.
  6. Testing linearity.
  7. Testing monotonicity.
  8. Lower bounds: triangle-freeness and bipartiteness in bounded-degree graphs.
  9. Estimating frequency moments in data streams.
  10. Estimating the entropy of a distribution.
  11. Tolerant Testing of Clustering.

 

Final Project information:
 A list of papers (roughly a subset of the large Princeton bibliography) from which you can select your project.

 

 Pointers to papers on which the lectures were based
(some pointers may need to be updated since have newer versions)

  1. The “binary-search-based” algorithm for testing one-dimensional monotonicity:
     Ergun, F., Kannan, S., Kumar, S.R., Rubinfeld, R., Vishwanthan, M.   Spot-checkers, JCSS 60 (2000), 717-751.
  2. The connectivity, k-connectivity, and cycle-freeness algorithms:
    Goldreich, O., Ron, D.   Property testing in bounded degree graphs, Algorithmica,  32  (2002), 302-343.
    the adaptation of connectivity to the general sparse (unbounded-degree) model appears in:
    Parnas, M., Ron, D.   Testing the diameter of graphs, Random Structures and Algorithms 20 (2002), 165-183.
  3. Testing bipartiteness of bounded-degree graphs:
    Goldreich, O., Ron, D.   A sublinear bipartite tester for bounded degree graphs, Combinatorica 19 (1999), 335-373.
  4. Testing bipartiteness of dense graphs:
    Goldreich, O., Goldwasser, S., Ron, D.   Property testing and its connection to learning and approximation, J. ACM 45 (1998), 653-750.
    An improved analysis appears in:
    Alon, N., Krivelevich, M.   Testing k-colorability, SIAM J. Discrete Math. 15 (2002), 211-227. 
  5. Testing bipartiteness of general graphs (only result was mentioned, but with no details):
    Kaufman, T., Krivelevich, M., Ron, D.   Tight bounds for testing bipartiteness in general graphs, SICOMP 33 (2004), 1441-1483.
  6. Testing triangle-freeness in dense graphs using the regularity lemma:
    Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.   Efficient testing of large graphs, Combinatorica 20 (2000), 451-476.
  7. Testing Linearity:
    Blum, M., Luby, M., Rubinfeld, R.   Self-testing/correcting with applications to numerical problems, J. Comput. Sys. Sci. 47 (1993), 549-595.
  8. Testing polynomials (over large fields):
    Rubinfeld, R., Sudan, M.   Robust characterizations of polynomials with applications to program testing, SIAM J. Comput. 25 (1996), 252-271.
    Testing polynomials over GF(2)
    Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.   Testing low-degree polynomials over GF(2), Proc. RANDOM-APPROX (2003), 188-199.
  9. Testing Monotonicity over the hypercube
    Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.   Testing monotonicity, Combinatorica 20 (2000), 301-337.
    Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S. Ron, D., Samorodnitsky, A.   Improved testing algorithms for monotonicity, Proc. RANDOM-APPROX (1999), 97-108.
    Testing Monotonicity over general posets:
    Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.   Monotonicity testing over general poset domains, Proc. 34th STOC (2002), 474-483.
  10. A lower bound for testing triangle-freeness
    Alon, N.   Testing subgraphs in large graphs, Random Structures and Algorithms 21 (2002), 359-370.
    The two-sided error arguments appears in:
    Alon, N., Shapira, A.   Testing subgraphs in directed graphs, Proc. 35th STOC (2003), 700-709.
  11. A lower bound for testing bipartiteness in bounded-degree graphs:
    Goldreich, O., Ron, D.   Property testing in bounded degree graphs, Algorithmica,  32  (2002), 302-343.
  12. Approximating Frequency moments:
    Alon, N., Matias, Y., Szegedy, M., The space complexity of approximating the frequency moments, J. Comput. Syst. Sci. 58 (1999), 137-147.
  13. Approximating the Entropy of a Distribution:
    Batu, T., Dasgupta, S., Kumar, R. Rubinfeld, R. The Complexity of Approximating the Entropy, SICOMP 35 (2005) 132-150.
  14. Tolerant Testing of Clustering
    Parnas, M., Ron, D., Rubinfeld, R., Tolerant Property Testing and Distance Approximation, ECCC, TR04-010, to appear in J. Comput. Syst. Sci.