Name
Abstract | ||
|---|---|---|
Motivated by questions in property testing, we search for linear error-correcting codes that have the "single local orbit" property: they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every "sparse" binary code whose coordinates are indexed by elements of for prime n , and whose symmetry group includes the group of non-singular affine transformations of , has the single local orbit property. (A code is sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (BCH codes) simple bases were not known. Our result gives the first short (O (n )-bit, as opposed to $\exp(n)$-bit) description of a low-weight basis for BCH codes. If 2 n *** 1 is a Mersenne prime, then we get that every sparse cyclic code also has the single local orbit. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03685-9_40 | APPROX '09 / RANDOM '09 Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
Keywords | DocType | Volume |
linear error-correcting code,binary code,single local orbit,every sparse cyclic code also has the single local orbit. keywords: locally testable codes,prime n,sparse cyclic code,succinct representation,bch code,single local orbit property,single local constraint,single orbit.,affine/cyclic invariance,symmetry group,dual-bch code | Journal | abs/0905.2919 |
ISSN | Citations | PageRank |
0302-9743 | 14 | 0.63 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elena Grigorescu | 1 | 192 | 24.75 |
| Tali Kaufman | 2 | 499 | 38.33 |
| Madhu Sudan | 3 | 5616 | 591.68 |