Abstract: Property testing deals with a relaxation of decision problems where one must determine whether an input belongs to a particular set, called property, or is far from it. For example, for a boolean formula φ on n variables, the associated property Pφ is a collection of n-bit strings that satisfy φ. The authors prove that there are 3CNF properties (properties for boolean formulae in 3CNF form) that require a linear number of queries, even for adaptive tests. In contrast, it is known that 2CNF properties can be tested with O(sqrt(n)) queries. I will briefly indroduce property testing and present the proof of hardness of 3CNF properties testing.
This paper appeared in STOC'03.