Testing of function that have small width branching programs
Ilan Newman · 2002
Combinatorial property testing, initiated formally by (Goldreich et al., 1996) and inspired by (Rubinfeld and Sudan, 1996), 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 being far from having the property. The main result here is that if G={g:{0,1}/sup n//spl rarr/{0,1}} is a family of Boolean functions that have read-once branching programs of width w, then for every n and /spl epsiv/>0 there is a randomized algorithm that always accepts every x/spl isin/{0,1}/sup n/ if g(x)=1, and rejects it with height probability if at least /spl epsiv/n bits of x should be modified in order for it to be in g/sup -1/(1). The algorithm queries (2w//spl epsiv/)/sup 0(w)/ many queries. In particular, for constant /spl epsiv/ and w, the query complexity is 0(1). This generalizes the results of (Alon et al., 1999) asserting that regular languages are efficiently (/spl epsiv/,O(1))-testable.