Next: On interactive proofs with
Up: Back at Weizmann (1998-2003)
Previous: On the (Im)possibility of
This work presents three theorems regarding testing graph
properties in the adjacency matrix representation.
These theorems relate to the project of
characterizing graph properties according to the complexity of
testing them (in the adjacency matrix representation).
Issues addressed include the existence of monotone
graph properties that are hard to test,
and canonical testers for graph properties.
Comments:
Authored by O. Goldreich and L. Trevisan. Appeared in
- Proceedings of 42nd FOCS, pages 460-469, 2001.
- Random Structures and Algorithms, to appear.
Oded Goldreich
2003-07-30