Property Testing and the Branching Program Size of Boolean Functions

摘要

Combinatorial property testing, initiated formally by Gol-dreich, Goldwasser, and Ron (1998) and inspired by Rubinfeld and Sudan (1996), deals with the relaxation of decision problems. Given a property P the aim is to decide whether a given input satisfies the property P or is far from having the property. For a family of boolean functions f = (f_n) the associated property is the set of 1-inputs of f. Newman (2002) has proved that properties characterized by oblivious read-once branching programs of constant width are testable, i.e., a number of queries that is independent of the input size is sufficient. We show that Newman's result cannot be generalized to oblivious read-once branching programs of almost linear size. Moreover, we present a property identified by restricted oblivious read-twice branching programs of constant width and by CNFs with a linear number of clauses, where almost all clauses have constant length, but for which the query complexity is Ω(n~(1/4)).