Computing with unreliable information

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing with unreliable information

Full text

Pdf (863 KB)

Source

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

Baltimore, Maryland, United States

Pages: 128 - 137

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

U. Feige	The Weizmann Institute of Science, Rehovot, Israel and T.J. Watson and Almaden Research Centers
D. Peleg	The Weizmann Institute of Science, Rehovot, Israel
P. Raghavan	IBM T.J. Watson Research Center, Yorktown Heights, NY
E. Upfal	IBM Almaden Research Center, San Jose, CA, and The Weizmann Institute of Science, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 23, Citation Count: 15

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/100216.100230 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	A.K. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SlAM Journal on Computing, 13(2):423-439, 1984.
	2	H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Math. Stat., 23:493-509, 1952.
	3	J. Hastad , T. Leighton , M. Newman, Reconfiguring a hypercube in the presence of faults, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.274-284, January 1987, New York, New York, United States [doi>10.1145/28395.28425]
	4	W. goeffding. Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc., 58:13-30, 1963.
	5	R.M. Karp. Personal communication. Berkeley, 1989.
	6	C. Kenyon-Mathieu and A.C. Yao. On evaluating boolean functions with unrealiable tests. Unpublished manuscript, Princeton Univ., 1989.
	7	D.J. Kleitman, A.R. Meyer, R.L. Rivest, J. Spencer, and K. Winldmann. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20:396-404, 1980.
	8	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	9	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	10	N. Pippenger. On networks of noisy gates. In g6th Annual Symposium on Foundations of Computer Science, pages 30-38, 1985.
	11	B. Ravikumar , K. Ganesan , K. B. Lakshmanan, On selecting the largest element in spite of erroneous information, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.88-99, February 1987, Passau, Germany
	12	B. Ravikumar and K.B. Lakshmanan. Coping with known patterns of lies in a search game. Theoretical Computer Science, 33:85-94, 1984.
	13	R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SlAM Journal on Computing, 14(2):396-409, 1985.
	14	M. SaYs and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In 27th Annual Symposium on Foundations of Computer Science, pages 29-38, Toronto, Ontario, 1986.
	15	J.P.M. Schalkwijk. A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback. 1EEE Trans. Info. Theory, 17(3):283-283, 1971.
	16	A.C. Yao and F.F. Yao. On fault-tolerant networks for sorting. SlAM Journal on Computing, 14:120- 128, 1985.

CITED BY 15

	William Evans , Nicholas Pippenger, Lower bounds for noisy Boolean decision trees, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.620-628, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Eyal Kushilevitz , Yishay Mansour, Computation in noisy radio networks, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 25-27, 1998, San Francisco, California, United States
	Ryan S. Borgstrom , S. Rao Kosaraju, Comparison-based search in the presence of errors, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.130-136, May 16-18, 1993, San Diego, California, United States
	Yuan Ma, An O(nlogn)-size fault-tolerant sorting network (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.266-275, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Richard M. Karp , Claire Kenyon , Orli Waarts, Error-resilient DNA computation, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.458-467, January 28-30, 1996, Atlanta, Georgia, United States
	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States
	Javed A. Aslam , Aditi Dhagat, Searching in the presence of linearly bounded errors, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.486-493, May 05-08, 1991, New Orleans, Louisiana, United States
	S. Muthukrishnan, On optimal strategies for searching in presence of errors, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 23-25, 1994, Arlington, Virginia, United States
	Mario Szegedy , Xiaomin Chen, Computing Boolean functions from multiple faulty copies of input bits, Theoretical Computer Science, v.321 n.1, p.149-170, June 16, 2004
	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States
	Micah Adler , Peter Gemmell , Mor Harchol-Balter , Richard M. Karp , Claire Kenyon, Selection in the presence of noise: the design of playoff systems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.564-572, January 23-25, 1994, Arlington, Virginia, United States
	B. J. Oommen , Jack R. Zgierski , D. Nussbaum, Deterministic Majority filters applied to stochastic sorting, Proceedings of the 42nd annual Southeast regional conference, April 02-03, 2004, Huntsville, Alabama
	Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Mark Braverman , Elchanan Mossel, Noisy sorting without resampling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.268-276, January 20-22, 2008, San Francisco, California
	Shlomi Dolev , Yinnon A. Haviv, Self-Stabilizing Microprocessor: Analyzing and Overcoming Soft Errors, IEEE Transactions on Computers, v.55 n.4, p.385-399, April 2006