Abstract:
For a boolean formula \phi on n variables, the associated property P_\phi is the collection of n-bit strings that satisfy \phi. We prove that there are 3CNF properties that require a linear number of queries, even for adaptive tests. This contrasts with 2CNF properties that are testable with O(\sqrt{n}) queries [FLNRRS2002]. Our results add two novel observations to the recent lower bounds of Bogdanov, Obata and Trevisan. First, notice that deciding P_\phi is easy once all the input is read. Thus, property testing can be hard even for easily computable properties. Second, for every bad instance (i.e. an assignment that does not satisfy \phi) there is a 3-bit query that proves this fact. Nevertheless, we show that finding such a short witness requires a linear number of queries. We provide a general characterization of linear properties that are hard to test, and in the course of the proof include a couple of observations which are of independent interest. 1. In the context of linear property testing, adaptive 2-sided error tests have no more power than non-adaptive 1-sided error tests. 2.Random linear codes with linear distance and constant rate are very far from being locally testable.