Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MONOTONE PROPERTIES:
Reports tagged with Monotone Properties:
TR01-010 | 25th January 2001
Oded Goldreich, Luca Trevisan

Three Theorems regarding Testing Graph Properties.

Revisions: 1


Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation. ... more >>>




ISSN 1433-8092 | Imprint