Research Abstracts - 2007

Abstract

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 Z_p^n to Z_p, first shown by M. Kiwi.

Research supported in part by NSF Award CCR-0514915.

References:

{BCLR} Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld, Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions. RANDOM 2004.

{BCHKS} Mihir Bellare and Don Coppersmith and Johan Haastad and Marcos Kiwi and Madhu Sudan. Linearity testing over characteristic two. IEEE Transactions on Information Theory, 42(6), 1781-1795, 1996.

{BLR} Manuel Blum and Michael Luby and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, 47(3), 549-595, 1993.

{GL} Oded Goldreich and Leonid Levin. A hard-core predicate for all one-way functions. Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 25--32, 1989

{GRS} Oded Goldreich and Ronitt Rubinfeld and Madhu Sudan. Learning polynomials with queries: The highly noisy case. SIAM Journal on Discrete Mathematics, 13(4):535-570, 2000.

{GSu} Venkatesan Guruswami and Madhu Sudan. List decoding algorithms for certain concatenated codes. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 181-190, 2000.

{KMS} Marcos Kiwi , Frederic Magniez , Miklos Santha. Exact and approximate testing/correcting of algebraic functions: A survey. Theoretical Aspects of Computer Science, Teheran, Iran, Springer-Verlag, LNCS 2292, 30-83, 2002.

{Kiwi} Marcos Kiwi. Testing and weight distributions of dual codes. Theoretical Computer Science, 299(1--3):81-106, 2003.

{STV}Madhu Sudan and Luca Trevisan and Salil Vadhan. Pseudorandom generators without the {XOR} lemma, Proceedings of the 31st Annual ACM Symposium on Theory of Computing 537-546, 1999.

{Tre} L. Trevisan. Some Applications of Coding Theory in Computational Complexity. Survey Paper. Quaderni di Matematica 13:347-424, 2004