Answers are grounded in this paper and cite their sources.
Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750] and inspired by Rubinfeld and Sudan [SIAM J. Comput., 25 (1996), pp. 252--271], deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x has the property or is "far" from having the property. The main result here is that, if G= \ gₙ:\0,1\ⁿ → \0,1\ \ is a family of Boolean functions which have oblivious read-once branching programs of width w, then, for every n and ε > 0, there is a randomized algorithm that always accepts every x ∈ \0,1\ⁿ if gₙ(x)=1 and rejects it with high probability if at least ε n bits of x should be modified in order for it to be in gn-1 (1). The algorithm makes (2ʷε)O(w) queries. In particular, for constant ε and w, the query complexity is O(1). This generalizes the results of Alon et al.\ [Proceedings of the40th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 1999, pp. 645--655] asserting that regular languages are ε-testable for every ε > 0.
No takes yet. Share an insight, caveat, or question.
Ilan Newman (2002) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: