Linear-time encodable and decodable error-correcting codes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear-time encodable and decodable error-correcting codes

Full text

Pdf (993 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 388 - 397

Year of Publication: 1995

ISBN:0-89791-718-9

Author

Daniel A. Spielman

Dept. of Mathematics, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 9

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/225058.225165 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.

	AC88	N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
	BZP77	L. A. Bassalygo, V. V. Zyablov, and M. S. Pinsker. Problems of complexity in the theory of correcting codes. Problems of Information Transmission, 13(3):166-175, 1977.
	Ga163	R. G. Gallager. LOW Density Parity-Check Codes. MIT Press, Cambridge, MA, 1963.
	GDP73	S. I. Gelfand, R. L. Dobrushin, and M. S. Pinsker. On the complexity of coding. In Second International Sym-posium on Information Theory, pages 177--184, Akademiai Kiado, Budapest, 1973.
	GG81	O. Gabber and Z. Galil. Explicit constructions of linear-sized superconcentrators. Journal of Computer and Sgstem Sciences, 22:407-420, 1981.
	Hei33	Hans Heilbrorm. Uber den primzahl.atz von Herrn Hoheisel. Mathematische Zeitschr~ft, 36:394-423, 1933.
	Jus76	Jorn Justesen. On the complexity of decoding Reed-Solomon codes. IEEE-TIT, 22(?) :237-238, March 1976.
	Kah93	Nabil Kahale. On the second eigenvalue and linear expansion of regular graphs. In Proc. of the 33rd FOCS, pages 296-303, 1993.
	Kuz73	A. V. Kuznetsov. Information storage in a memory assembled from unreliable components. Prob/ems of ln~or-mation Transmission, 9(3):254-264, 1973.
	LPS88	A. Lubotzky, R. Phillips, and P. Sarnak. Ramanu-jan graphs. Combinatorics, 8(3):261-277, 1.988.
	Mar88	G. A. Margulis. Explicit group theoretical construc-tions of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Infor-mation Transmission, 24(1):39-46, July 1988.
	MS77	F. J. MacWilliams and N. J. A. Sloane. The The-ory of Error- Correcting Codes. North Holland, Amsterdam, 1977.
	Pip77	Nicholas Pippenger. Superconcentrators. SIAM Journal on Computmg, 6:298-304, 1977.
	Pip93	Nicholas Pippenger, Self-routing superconcentrators, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.355-361, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167195]
	Sar77	Dilip V, Sarwate. On the complexity of decoding Goppa codes. IEEE-TIT, 23(?) :515-516, July 1977.
	Sav71	John E. Savage. The complexity of decoders-part II: Computational work and decoding time. IEEE- TIT, 17(1):77-85, January 1971.
	SS94	Michael Sipser and Daniel A. Spielman. Expander codes. In Proc. of the 35th FOCS, pages 566-576, 1994.
	Va176	L. G. Valiant. Graph-theoretic properties in compu-tational complexity. Journal of Computer and System Sci-ences, 13:423-432, 1976.
	Ziv67	Jacob Ziv. Asymptotic performance and complexity of a coding scheme for memory less than nels. IEEE- TIT, 13(3):356-359, July 1967.
	ZP76	V. V. Zyablov and M. S. Pinsker. Estimation of the error-correction complexity of Gallager low-density codes. Problems of Information Transmission, 11(1):18-28, May 1976.

CITED BY 9

	Claudia Bertram-Kretzberg , Thomas Hofmeister , Hanno Lefmann, Sparse 0-1-matrices and forbidden hypergraphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.181-187, January 25-27, 1998, San Francisco, California, United States
	Leonard J. Schulman , David Zuckerman, Asymptotically good codes correcting insertions, deletions, and transpositions, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.669-674, January 05-07, 1997, New Orleans, Louisiana, United States
	Peter Bro Miltersen, Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.556-563, January 25-27, 1998, San Francisco, California, United States
	Rocco A. Servedio, Computational sample complexity and attribute-efficient learning, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.701-710, May 01-04, 1999, Atlanta, Georgia, United States
	Harold N. Gabow, Using expander graphs to find vertex connectivity, Journal of the ACM (JACM), v.53 n.5, p.800-844, September 2006
	André Gronemeier, A note on the decoding complexity of error-correcting codes, Information Processing Letters, v.100 n.3, p.116-119, 15 November 2006
	Hanno Lefmann , Pavel Pudlák , Petr Savicky, On Sparse Parity Check Matrices, Designs, Codes and Cryptography, v.12 n.2, p.107-130, Oct. 1997
	Hanno Lefmann, Sparse Parity-Check Matrices over ${GF(q)}$, Combinatorics, Probability and Computing, v.14 n.1, p.147-169, January 2005
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Cryptography with constant computational overhead, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada