ECCC-Report TR08-033https://eccc.weizmann.ac.il/report/2008/033Comments and Revisions published for TR08-033en-usFri, 21 Mar 2008 22:22:25 +0200
Paper TR08-033
| 2-Transitivity is Insufficient for Local Testability |
Elena Grigorescu,
Tali Kaufman,
Madhu Sudan
https://eccc.weizmann.ac.il/report/2008/033A 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
Sudan~\cite{Kauf-Sudan}
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.
Fri, 21 Mar 2008 22:22:25 +0200https://eccc.weizmann.ac.il/report/2008/033