Name
Abstract | ||
|---|---|---|
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. (Trans Inf Theory, 51(11):4032---4039, 2005) had conjectured that the presence of a single low-weight codeword in the dual, and "2-transitivity" of the code (i.e., the code being 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 & Sudan (STOC, 2008) 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00037-012-0055-3 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | DocType | Volume |
2-transitive group,property testing,basic goal,algebraic property testing,complementary virtue,affine transformation,trans inf theory,local testability,error-correcting code,property testable,binary linear error-correcting code | Journal | 22 |
Issue | ISSN | Citations |
1 | 1016-3328 | 14 |
PageRank | References | Authors |
0.64 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elena Grigorescu | 1 | 192 | 24.75 |
| Tali Kaufman | 2 | 499 | 38.33 |
| Madhu Sudan | 3 | 5616 | 591.68 |