Next: On the Complexity of
Up: Sabbatical at MIT (1996-1998)
Previous: Sabbatical at MIT (1996-1998)
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).
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