$next$ $up$ $previous$
Next: On the Complexity of Up: Sabbatical at MIT (1996-1998) Previous: Sabbatical at MIT (1996-1998)

Property Testing and its connection to Learning and Approximation

This paper initiates a general treatment of Property Testing, while focusing on testing of graph properties in the adjacency matrix representation. The main results are testers for a variety of graph partition problems all having query complexity that is independent of the size of the graph (but rather depends only on the approximation parameter).

$\fbox{\begin{minipage}{40em} {\bf Abstract ({rev.}):} {We consider the question... ...o the property being tested, if it holds for the input graph.} \end{minipage}}$

Comments: Authored by O. Goldreich, S. Goldwasser and D. Ron. Appeared in

Proc. of the 37th FOCS, pp. 339-348, 1996.
Jour. of the ACM, pages 653-750, July 1998.

Oded Goldreich
2003-07-30