A large lower bound on the query complexity of a simple boolean function

Combinatorial property testing, initiated formally by Goldreich, 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=(fn) the associated property is the set of 1-inputs of f. Here, the known lower bounds on the query complexity of properties identified by boolean functions representable by (very) restricted branching programs of small size is improved up to Ω(n1/2), where n is the input length.