Local Decoding and Testing for Homomorphisms

Locally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, low-degree polynomials over finite fields, in the construction of these objects is well studied. However the role of group homomorphisms in the construction of such codes is not as widely studied. Here we initiate a systematic study of local decoding of codes based on group homomorphisms. We give an efficient list decoder for the class of homomorphisms from any abelian group

G

to a fixed abelian group

H

. The running time of this algorithm is bounded by a polynomial in log|

G

| and an agreement parameter, where the degree of the polynomial depends on

H

. Central to this algorithmic result is a combinatorial result bounding the number of homomorphisms that have large agreement with any function from

G

to

H

. Our results give a new generalization of the classical work of Goldreich and Levin, and give new abstractions of the list decoder of Sudan, Trevisan and Vadhan. As a by-product we also derive a simple(r) proof of the local testability (beyond the Blum-Luby-Rubinfeld bounds) of homomorphisms mapping

${\mathbb{Z}}_p^n$

to ℤ

p

, first shown by M. Kiwi.