Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-020 | 7th March 2008 00:00

Decodability of Group Homomorphisms beyond the Johnson Bound


Authors: Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan
Publication: 7th March 2008 15:39
Downloads: 3657


Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from a fraction of errors arbitrarily close to its distance. At the heart of this result is the following combinatorial result: There is a fixed polynomial $p(\cdot)$ 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 $\Lambda$, then for every $\epsilon> 0$ and every function $f:G\to H$, the number of homomorphisms that have agreement $\Lambda + \epsilon$ with $f$ is at most $p(1/\epsilon)$.

We thus give a broad class of codes whose list-decoding radius 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 certain ``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.

ISSN 1433-8092 | Imprint