# 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.

• Introduction: Sublinear algorithms in general and
property testing
algorithms in particular.
• Different Models for testing graph properties:

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.

• Algebraic properties and locally testable codes:
Linearity and Low-Degree Polynomials.
• Properties of functions: Monotonicity, and basic properties of Boolean functions.
• Clustering.
• Minimum Spanning Tree.
• Proximity of Distributions.
• Streaming algorithms.

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.

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.

Other Information

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

Final Project information:
(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:
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.