Abstract
Ulam proposed the problem of determining an optimum strategy for finding an integer x ∈ {1, 2, ..., n} using binary queries (i.e., queries with yes/no answer) in which the responses to up to k queries (for a fixed k) can be incorrect. This problem has been extensively studied for the past fifty years. The paper by Rivest et al. [9] that made a major advance in Ulam’s problem introduced a restricted type of error in responses known as half-lies. Rivest et al. presented a lower-bound on the minimax complexity of the half-lie version of Ulam’s search problem. Here we present a new algorithm that improves the previous upper-bound for the half-lie problem (in the case of k = 1) for all sufficiently large values of n. Specifically, we show that the number of queries of the form ’Is x > s?’ sufficient (in the worst-case) to find an unknown integer x ∈ {1, 2, ..., n}, when the responder’s ’yes’ answers are always true, but at most one of the ’no’ answers may be false, is at most ⌈log2((n + 4.5) ln (n + 4.5) − 4.5 ln (4.5))⌉. We also present an improvement to Rivest et al.’s lower-bound for the special case of n = 106.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aslam, J., Dhagat, A.: Searching in the presence of linear bounded errors. In: Proc. of 23rd ACM Symp. on Theory of Computing, pp. 487–493 (1991)
Cicalese, F., Mundici, D.: Optimal Coding with One Asymmetric Error: Below the Sphere Packing Bound. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol. 1858, pp. 159–169. Springer, Heidelberg (2000)
Ellis, R., Yan, C.: Ulam’s pathological liar game with one half-lie. International Journal of Mathematics and Mathematical Sciences 2004(29), 1523–1532 (2004)
Innes, D.: Searching with a lie using only comparison questions. In: International Conference on Computing and Information, pp. 87–90 (1992)
Gao, F., Guibas, L.J., Kirkpatrick, D.G., Laaser, W.T., Saxe, J.: Finding extrema with unary predicates. Algorithmica 9, 591–600 (1993)
Pelc, A.: Solution to Ulam’s problem on searching with a lie. Journal of Combinatorial Theory Series A 40(9), 1081–1089 (1991)
Pelc, A.: Searching games with errors 50 years of coping with liars. Theoretical Computer Science 270, 71–109 (2002)
Ravikumar, B., Lakshmanan, K.B.: Coping with known patterns of lies in a search game. Theoretical Computer Science 33, 85–94 (1984)
Rivest, R., Meyer, A.R., Kleitman, D.J., Spencer, J., Winklmann, K.: Coping with errors in binary search procedures. Journal of Computer and System Sciences 20(3), 396–404 (1980)
Spencer, J.: Guess a number - with lying. Mathematics Magazine 57(2) (1984)
Spencer, J.: Ulam’s searching game with a fixed number of lies. Theoretical Computer Science 95, 307–321 (1992)
Spencer, J., Winkler, P.: Three thresholds for a liar. Combinatorics, Probability and Computing 1(1), 81–93 (1992)
Spencer, J., Yan, C.H.: The half-lie problem. Journal of Combinatorial Theory, Series A 103, 69–89 (2003)
Ulam, S.: Adventures of a Mathematician. Scribner, New York (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ravikumar, B., Innes, D. (2014). An Improved Upper-Bound for Rivest et al.’s Half-Lie Problem. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds) Theory and Applications of Models of Computation. TAMC 2014. Lecture Notes in Computer Science, vol 8402. Springer, Cham. https://doi.org/10.1007/978-3-319-06089-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-06089-7_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06088-0
Online ISBN: 978-3-319-06089-7
eBook Packages: Computer ScienceComputer Science (R0)