Decodability of group homomorphisms beyond the johnson bound

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decodability of group homomorphisms beyond the johnson bound

Full text

Pdf (301 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 40th annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

SESSION: 7A table of contents

Pages 275-284

Year of Publication: 2008

ISBN:978-1-60558-047-0

Authors

Irit Dinur	Weizmann Institute of Science, Rehovot, Israel
Elena Grigorescu	Massachusetts Institute of Technology, Cambridge, MA, USA
Swastik Kopparty	Massachusetts Institute of Technology, Cambridge, MA, USA
Madhu Sudan	Massachusetts Institute of Technology, Cambridge, MA, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 68, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1374376.1374418 What is a DOI?

ABSTRACT

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 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(•) 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 Λ, then for every ε> 0 and every function f:G -> H, the number of homomorphisms that have agreement Λ + ε with f is at most p(1/ε). 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Adi Akavia , Shafi Goldwasser , Samuel Safra, Proving Hard-Core Predicates Using List Decoding, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.146, October 11-14, 2003
	2	Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Decodability of Group Homomorphisms beyond the Johnson Bound. Electronic Colloquium on Computational Complexity (ECCC), 15(TR08-020), 2008.
	3	A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509933]
	4	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	5	Oded Goldreich , Ronitt Rubinfeld , Madhu Sudan, Learning Polynomials with Queries: The Highly Noisy Case, SIAM Journal on Discrete Mathematics, v.13 n.4, p.535-570, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480198344540]
	6	Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Local decoding and testing for homomorphisms. In APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 375--385. Springer, 2006.
	7	V. Guruswami and M. Sudan. Extensions to the johnson bound, 2001.
	8	Venkatesan Guruswami and Atri Rudra. Explicit capacity-achieving list-decodable codes. Electronic Colloquium on Computational Complexity (ECCC), (133), 2005.
	9	Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, SIAM Journal on Computing, v.22 n.6, p.1331-1348, Dec. 1993 [doi>10.1137/0222080]
	10	Serge Lang. Algebra. Addison-Wesley, 1965.
	11	Yishay Mansour, Randomized Interpolation and Approximationof Sparse Polynomials, SIAM Journal on Computing, v.24 n.2, p.357-368, April 1995 [doi>10.1137/S0097539792239291]
	12	Farzad Parvaresh , Alexander Vardy, Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.285-294, October 23-25, 2005 [doi>10.1109/SFCS.2005.29]
	13	Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301397]
	14	A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50, 2004