Name
Abstract | ||
|---|---|---|
Given a pair of finite groups G and H, the set of homomor- phisms from G to H form an error-correcting code where codewords dier in at least 1 /2 the coordinates. We show that for every pair of abelian groups G and H, the resulting code is (locally) list-decodable from a fraction of errors arbi- trarily close to its distance. At the heart of this result is the following combinatorial result: There is a fixed polynomial p(·) such that for every pair of abelian groups G and H, if the maximum fraction of agreement between two distinct homomorphisms from G to H is , then for every > 0 and every function f : G ! H, the number of homomorphisms that have agreement + with f is at most p(1/ ). We thus give a broad class of codes whose list-decoding ra- dius exceeds the "Johnson bound". Examples of such codes are rare in the literature, and for the ones that do exist, "combinatorial"techniques to analyze their list-decodability are limited. Our work is an attempt to add to the body of such techniques. We use the fact that abelian groups decompose into simpler ones and thus codes derived from homomorphisms over abelian groups may be viewed as cer- tain "compositions" of simpler codes. We give techniques to lift list-decoding bounds for the component codes to bounds for the composed code. We believe these techniques may be of general interest. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1374376.1374418 | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
h form,abelian group,hadamard codes,component code,following combinatorial result,distinct homomorphisms,sublinear time algorithms,group homomorphisms,abelian groups decompose,fixed polynomial p,simpler code,error-correcting code,resulting code,list decoding | Discrete mathematics,Abelian group,Combinatorics,Group code,Polynomial,Sublinear algorithms,Johnson bound,Homomorphism,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 020 | 0737-8017 |
Citations | PageRank | References |
5 | 0.43 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Elena Grigorescu | 2 | 192 | 24.75 |
| Swastik Kopparty | 3 | 384 | 32.89 |
| Madhu Sudan | 4 | 5616 | 591.68 |