0510.7410

Administrative Information. Lectures: Mondays 4-6 Lecturer: Dana Ron,
Office hours: Can be coordinated by email. Brief Course Description: 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.

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.

Other Information

Notes

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

- Notes for lecture #1: Introduction
- Property testing
of graphs: models and results in bounded degree graphs (part I).
- Testing
k-connectivity and bipartiteness in bounded-degree/sparse graphs.
- Testing bipartiteness in dense graphs (from
Design and Analysis of Algorithms course).
- Applying the
regularity lemma.
- Testing linearity.
- Testing monotonicity.
- Lower bounds:
triangle-freeness and bipartiteness in bounded-degree graphs.
- Estimating
frequency moments in data streams.
- Estimating the
entropy of a distribution.
- 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)

- 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. - 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. - Testing bipartiteness
of bounded-degree graphs:

**Goldreich, O., Ron, D.**A sublinear bipartite tester for bounded degree graphs, Combinatorica 19 (1999), 335-373. - 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. - 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. - 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. - Testing Linearity:

**Blum, M., Luby, M., Rubinfeld, R.**Self-testing/correcting with applications to numerical problems, J. Comput. Sys. Sci. 47 (1993), 549-595. - 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. - 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. - 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. - 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. - 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. - 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. - 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.