Abstract
We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More realistic seems the “burst error model”, in which all faults occur in some small time interval.
Like previous work, our problem can best be modelled as a two-player perfect information game, in which one player (“Paul”) has to guess a number x from {1, ..., n} using Yes/No-questions, which the second player (“Carole”) has to answer truthfully apart from few lies. In our setting, all lies have to be in a consecutive set of k rounds.
We show that (for big n) Paul needs roughly logn+loglogn+k rounds to determine the number, which is only k more than the case of just one single lie.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Borgstrom, R.S., Kosaraju, S.R.: Comparison-based search in the presence of errors. In: STOC, pp. 130–136 (1993)
Cicalese, F., Mundici, D.: Optimal binary search with two unreliable tests and minimum adaptiveness. In: Nešetřil, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 257–266. Springer, Heidelberg (1999)
Pelc, A.: Solution of Ulam’s problem on searching with a lie. J. Comb. Theory, Ser. A 44(1), 129–140 (1987)
Pelc, A.: Searching with known error probability. Theor. Comput. Sci. 63(2), 185–202 (1989)
Pelc, A.: Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci. 270(1-2), 71–109 (2002)
Rényi, A.: On a problem of information theory. MTA Mat. Kut. Int. Kozl. 6B, 505–516 (1961)
Rényi, A.: Napl’o az információelméletről, Gondolat, Budapest (1976), (English translation: A Diary on Information Theory, Wiley, New York, 1984)
Spencer, J.: Ulam’s searching game with a fixed number of lies. Theor. Comput. Sci. 95(2), 307–321 (1992)
Ulam, S.M.: Adventures of a Mathematician, p. 281. Scribner, New York (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doerr, B., Lengler, J., Steurer, D. (2006). The Interval Liar Game. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_33
Download citation
DOI: https://doi.org/10.1007/11940128_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.