Chinese remaindering with errors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Chinese remaindering with errors

Full text

Pdf (820 KB)

Source

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

Atlanta, Georgia, United States

Pages: 225 - 234

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Oded Goldreich	Department of Computer Science, Weizmann Institute of Science
Dana Ron	Department of Electrical Engineering - Systems, Tel Aviv University
Madhu Sudan	Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 29, Citation Count: 4

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/301250.301309 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	M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
	2	A. AMIR, R. BEIGEL, AND W. GASARCH. Cheatable, P-terse, and P-superterse sets, manuscript, Dec. 1989.
	3	Sigal Ar , Richard J. Lipton , Ronitt Rubinfeld , Madhu Sudan, Reconstructing Algebraic Functions from Mixed Data, SIAM Journal on Computing, v.28 n.2, p.487-510, April 1999 [doi>10.1137/S0097539796297577]
	4	E. R. BERLEKAMP. Algebraic Coding Theory. McGraw Hill, New York, 1968.
	5	E. R. B~;aLrgAMr. Bounded Distance +1 Soft- Decision Reed-Solomon Decoding. {EEE Transactions on Information Theory, 42(3):704-720, 1996.
	6	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	7	A. BORODIN AND I. MUNRO. The Computational Com- Elsevier Publishing Company, New York, 1975.
	8	Jin-yi Cai , Lane A. Hemachandra, A note on enumerative counting, Information Processing Letters, v.38 n.4, p.215-219, May 31, 1991 [doi>10.1016/0020-0190(91)90103-O]
	9	J. C^I, A. PAY^N, AND D. SIVAKUMAR. On the Hardness of Permanent. STAACS, t999.
	10	I. M. DUURSMA. Decoding codes from curves and cyclic codes. Ph.D. Thesis, Eindhoven, 1993.
	11	P. ELIAS. List decoding for noisy channels. Technical Report 335, Research Lab. of Electronics, MIT, 1957.
	12	P. ELIAS. Error-correcting codes for list decoding. IEEE Trans. on Information Theory, 37:5-12. 1991.
	13	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]
	14	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]
	15	O. GOLDaEICH, D. RaN AND M. SUDAN. Chinese Remaindering with Errors. Available from ECCC, 1998.
	16	O. Goldreich , R. Rubinfeld , M. Sudan, Learning polynomials with queries: The highly noisy case, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.294, October 23-25, 1995
	17	S. GOLDWASSER AND S. M~CALI. Probabilistic Encryl~ tion. JCSS, Vol. 28, No. 2, pages 270-299, t984.
	18	Venkatesan Guruswami , Madhu Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.28, November 08-11, 1998
	19	Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
	20	R. M. K^RP AND M. O. R^BtN. Efficient randomized pattern-matching Mgorithms. Technical report TR-31- 81, Aiken Computation Laboratory, Harvard University, 1981.
	21	D.E. KNUTH. The ~nalysis of algorithms. Acres du Congres International des Mathematiciens, Tome 3, 269-274, 1970.
	22	R. KOTTEa. A unified description of an error locating procedure for linear codes. Proceedings of Algebraic and Combinatorial Coding Theory, Voneshta Voda, Bulgaria, 1992.
	23	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	24	A. K. LENSTRA, H. W. LENSTRA AND L. LOVASZ. Factoring polynomials with rationaJ coefficients. Mathematische Annalen, 261:515-534, 1982.
	25	H. W. LENSTRA. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8: 538-548, 1983.
	26	R. J. LEPTON. New directions in testing. Distributed Computing and Cryptography, J. Feigenbaum and M. Merritt (ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American M~thematics Society, 2:191-202, 1991.
	27	L. Lov~sz. An Algorithmic Theory of Numbers, Graphs and Convexity. SIAM Publications, 1986.
	28	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	29	F. J. MACW!I, LIAMS AND N. J. A. SLOANE. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1981.
	30	J. L. MAssEY. Shift register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15:122-127, 1969.
	31	R. PELLIK^AN. On decoding linear codes by error correcting pairs. Eindhoven University of Technology, preprint, 1988.
	32	W. W. PETERSON. Encoding and error-correction procedures for Bose-Chaudhuri codes. IRE Transactions on Information Theor); IT-60:459-470, 1960.
	33	A. SCHONHAGE AND V. STRASSEN. Schne!le multiplikation grosset zahlen. Computing, 7:281-292, 1971.
	34	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
	35	M. Amin Shokrollahi , Hal Wasserman, Decoding algebraic-geometric codes beyond the error-correction bound, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.241-248, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276753]
	36	M. SIPsEa AND D. A. SPIELMAN. Expander codes. {EEE Transactions on Information Theory, 42(6):I710-1722, 1996.
	37	D. A. SPIELMAN. Linear-time encodable and decodable error-correctiu~ codes. IEEE Transactions on In}ormation Theory, 42(6):1723-1732, 1996.
	38	Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
	39	Jacobus Hendricus van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
	40	L. G. VALIANT. The complexity of computing the permanent. TheoreticaI Computer Science, 8(2):189-201, April 1979.
	41	Alexander Vardy, Algorithmic complexity in coding theory and the minimum distance problem, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.92-109, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258559]
	42	L. WELCH AND F... R. BERLEKAMP. Error correction of aJgebraic block codes. US Patent Number 4,633,470, issued December 1986.

CITED BY 4

	Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Journal of Computer and System Sciences, v.64 n.4, p.768-784, June 2002
	Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.265-272, May 21-23, 2000, Portland, Oregon, United States
	Johan Håstad , Mats Nåslund, The security of all RSA and discrete log bits, Journal of the ACM (JACM), v.51 n.2, p.187-230, March 2004
	Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity Via Uniform Reductions, Computational Complexity, v.16 n.4, p.331-364, December 2007