loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 IEEE 23rd Annual Conference on Computational Complexity
2-Transitivity Is Insufficient for Local Testability
June 22-June 26
ISBN: 978-0-7695-3169-4
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 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 counter examples to natural conjectures.
Index Terms:
property testing, sublinear time algorithms, error correcting codes
Citation:
Elena Grigorescu, Tali Kaufman, Madhu Sudan, "2-Transitivity Is Insufficient for Local Testability," ccc, pp.259-267, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.