Searching in the presence of linearly bounded errors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Searching in the presence of linearly bounded errors

Full text

Pdf (720 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 486 - 493

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Javed A. Aslam	Massachusetts Institute of Technology, Cambridge
Aditi Dhagat	Massachusetts Institute of Technology, Cambridge

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 11

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

	AD90	Javed Aslam and Aditi Dhagat. On-line algorithms for 2-coloring hypergraphs via chip games. Technical Report TM-439, MIT Laboratory for Computer Science, 1990.
	AL86	D. Angluin and P. Laird. Identifying kcnf formulas from noisy examples. Technical Report YALEU/DCS/TR-478, Yale University, 1986.
	Ber68	E. Berlekamp. Error Correcting Codes, pages 61-85. Wiley, N.Y., 1968.
	FPRU90	U. Feige , D. Peleg , P. Raghavan , E. Upfal, Computing with unreliable information, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.128-137, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100230]
	Fra90	Michael Frazier. Searching with a nonconstant number of lies, 1990.
	GKS90	S. Goldman, M. Kearns, and R. Schapire. Exact identification of circuits using fixed points of amplification functions. In 31st Symposium on Foundalions of Computer Science, 1990.
	KL88	Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
	KY90	Claire Kenyon and Andrew C. Yao. On evaluation of boolean functions with unreliable tests. Internalional journal of Foundations of Compuler Science, 1(1):1-10, 1990.
	Pel87	Andrzej Pelc, Solution of Ulam's problem on searching with a lie, Journal of Combinatorial Theory Series A, v.44 n.1, p.129-140, Jan. 1987 [doi>10.1016/0097-3165(87)90065-3]
	Pel88	Andrzej Pelc, Prefix search with a lie, Journal of Combinatorial Theory Series A, v.48 n.2, p.165-173, July 1988 [doi>10.1016/0097-3165(88)90003-9]
	Pel89a	A. Pelc, Detecting errors in searching games, Journal of Combinatorial Theory Series A, v.51 n.1, p.43-54, May 1989 [doi>10.1016/0097-3165(89)90075-7]
	Pel89b	A. Pelc, Searching with known error probability, Theoretical Computer Science, v.63 n.2, p.185-202, Feb. 1989 [doi>10.1016/0304-3975(89)90077-7]
	RGL87	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
	RL84	B. Ravikumar and K. B. Lakshmanan. Coping with known patterns of lies in a search game. Theorelical Computer Science, 33:85- 94, 1984.
	RMK+80	R.L. Rivest, A. R. Meyer, D. J. Kleitman, K. Winklmann, and J. Spencer. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20:396-404, 1980.
	SW90	Joel Spencer and Peter Winkler. Three thresholds for a liar. Preprint, 1990.

CITED BY 11

	Alberto Pedrotti, Playing by searching: two strategies against a linearly bounded liar, Theoretical Computer Science, v.282 n.2, p.285-302, 10 June 2002
	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
	Ferdinando Cicalese , Daniele Mundici , Ugo Vaccaro, Least adaptive optimal search with unreliable tests, Theoretical Computer Science, v.270 n.1-2, p.877-893, January
	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
	Aditi Dhagat , Peter Gács , Peter Winkler, On playing “Twenty Questions” with a liar, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.16-22, September 1992, Orlando, Florida, United States
	Ming-Yang Kao , John H. Reif , Stephen R. Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.441-447, January 25-27, 1993, Austin, Texas, United States
	Andrzej Pelc, Searching games with errors---fifty years of coping with liars, Theoretical Computer Science, v.270 n.1-2, p.71-109, January
	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
	Irene Finocchi , Giuseppe F. Italiano, Sorting and searching in the presence of memory faults (without redundancy), Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Richard M. Karp , Robert Kleinberg, Noisy binary search and its applications, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.881-890, January 07-09, 2007, New Orleans, Louisiana
	Irene Finocchi , Fabrizio Grandoni , Giuseppe F. Italiano, Resilient search trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.547-553, January 07-09, 2007, New Orleans, Louisiana