Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOUND:
Reports tagged with bound:
TR06-103 | 5th July 2006
Oded Lachish, Ilan Newman, Asaf Shapira

Space Complexity vs. Query Complexity

Combinatorial property testing deals with the following relaxation
of decision problems: Given a fixed property and an input $x$, one
wants to decide whether $x$ satisfies the property or is ``far''
from satisfying it. The main focus of property testing is in
identifying large families of properties that can be ... more >>>




ISSN 1433-8092 | Imprint