On the efficiency of local decoding procedures for error-correcting codes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the efficiency of local decoding procedures for error-correcting codes

Full text

Pdf (732 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 80 - 86

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Jonathan Katz	Department of Computer Science, Columbia University
Luca Trevisan	Department of Computer Science, Columbia University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 41, Citation Count: 18

Additional Information:

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/335305.335315 What is a DOI?

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	Andris Ambainis, Upper Bound on Communication Complexity of Private Information Retrieval, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.401-407, July 07-11, 1997
	2	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
	3	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
	4	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
	5	László Babai , Lance Fortnow , Noam Nisan , Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Computational Complexity, v.3 n.4, p.307-318, Oct. 1993 [doi>10.1007/BF01275486]
	6	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	7	Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
	8	Joan Feigenbaum , Lance Fortnow, Random-self-reducibility of complete sets, SIAM Journal on Computing, v.22 n.5, p.994-1005, Oct. 1993 [doi>10.1137/0222061]
	9	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	10	Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
	11	O. Goldreich. Personal communication. September 1999.
	12	L. Levin. Research overview. http://ww~, cs. bu. edu/f ac/lnd/res earch/res, html.
	13	R. Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, 1989.
	14	E. Mann. Private access to distributed information. Master's Thesis, Technion, 1998.
	15	Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195132]
	16	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]

CITED BY 18

	Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Batch codes and their applications, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Journal of Computer and System Sciences, v.69 n.3, p.395-420, November 2004
	Amos Beimel , Yuval Ishai , Eyal Kushilevitz, General constructions for information-theoretic private information retrieval, Journal of Computer and System Sciences, v.71 n.2, p.213-247, August 2005
	Zeev Dvir , Amir Shpilka, Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Dungjade Shiowattana , Satyanarayana V. Lokam, An optimal lower bound for 2-query locally decodable linear codes, Information Processing Letters, v.97 n.6, p.244-250, 31 March 2006
	Amit Deshpande , Rahul Jain , T. Kavitha , Satyanarayana V. Lokam , Jaikumar Radhakrishnan, Lower bounds for adaptive locally decodable codes, Random Structures & Algorithms, v.27 n.3, p.358-378, October 2005
	Adi Akavia , Oded Goldreich , Shafi Goldwasser , Dana Moshkovitz, On basing one-way functions on NP-hardness, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Oded Goldreich , Madhu Sudan, Locally testable codes and PCPs of almost-linear length, Journal of the ACM (JACM), v.53 n.4, p.558-655, July 2006
	Tomoyuki Yamakami, Quantum list decoding from quantumly corrupted codewords for classical block codes of polynomially small rate, Proceedings of the thirteenth Australasian symposium on Theory of computing, p.153-162, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Sergey Yekhanin, Towards 3-query locally decodable codes of subexponential length, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Amir Shpilka, Interpolation of depth-3 arithmetic circuits with two multiplication gates, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Sergey Yekhanin, Towards 3-query locally decodable codes of subexponential length, Journal of the ACM (JACM), v.55 n.1, p.1-16, February 2008
	Moni Naor , Guy N. Rothblum, The complexity of online memory checking, Journal of the ACM (JACM), v.56 n.1, p.1-46, January 2009
	Klim Efremenko, 3-query locally decodable codes of subexponential length, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA