
Research
Abstracts  2007 
Local Decoding and Testing for HomomorphismsElena Grigorescu, Swastic Kopparty & Madhu SudanAbstractLocally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, lowdegree 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 byproduct we also derive a simple(r) proof of the local testability (beyond the BlumLubyRubinfeld bounds) of homomorphisms mapping Z_p^n to Z_p, first shown by M. Kiwi. Research supported in part by NSF Award CCR0514915. References:{BCLR} Michael BenOr, Don Coppersmith, Michael Luby, Ronitt Rubinfeld, NonAbelian Homomorphism Testing, and Distributions Close to their SelfConvolutions. 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), 17811795, 1996. {BLR} Manuel Blum and Michael Luby and Ronitt Rubinfeld. SelfTesting/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, 47(3), 549595, 1993. {GL} Oded Goldreich and Leonid Levin. A hardcore predicate for all oneway functions. Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 2532, 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):535570, 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, 181190, 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, SpringerVerlag, LNCS 2292, 3083, 2002. {Kiwi} Marcos Kiwi. Testing and weight distributions of dual codes. Theoretical Computer Science, 299(13):81106, 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 537546, 1999. {Tre} L. Trevisan. Some Applications of Coding Theory in Computational Complexity. Survey Paper. Quaderni di Matematica 13:347424, 2004 

