CSAIL Publications and Digital Archive header
bullet Research Abstracts Home bullet CSAIL Digital Archive bullet Research Activities bullet CSAIL Home bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line

 

Research Abstracts - 2007
horizontal line

horizontal line

vertical line
vertical line

Local Decoding and Testing for Homomorphisms

Elena Grigorescu, Swastic Kopparty & Madhu Sudan

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

 

vertical line
vertical line
 
horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu