Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-033 | 21st March 2008 00:00

2-Transitivity is Insufficient for Local Testability


Authors: Elena Grigorescu, Tali Kaufman, Madhu Sudan
Publication: 21st March 2008 22:22
Downloads: 2926


A basic goal in Property Testing is to identify a
minimal set of features that make a property testable.
For the case when the property to be tested is membership
in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}
had conjectured that the presence of a {\em single} low weight
code in the dual, and ``2-transitivity'' of the code (i.e.,
the code is invariant under a 2-transitive group of permutations
on the coordinates of the code) suffice to get local testability.
We refute this conjecture by giving a family of error correcting
codes where the coordinates of the codewords form a large
field of characteristic two, and the code is invariant under
affine transformations of the domain.
This class of properties was introduced by Kaufman and
as a setting where many results in algebraic property testing
generalize. Our result shows a complementary virtue: this family also
can be useful in producing counterexamples to natural conjectures.

ISSN 1433-8092 | Imprint