TR03-006 Authors: Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

Publication: 27th January 2003 19:26

Downloads: 1893

Keywords:

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.