Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-006 | 23rd January 2003 00:00

3CNF Properties are Hard to Test


Authors: Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova
Publication: 27th January 2003 19:26
Downloads: 2861


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.

ISSN 1433-8092 | Imprint