Strategies for the Renyi-Ulam Game with fixed number of lies

Deppe C (2004)
THEORETICAL COMPUTER SCIENCE 314(1-2): 45-55.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Abstract / Bemerkung
We consider the problem of finding the minimal number L-l(M) of binary questions needed to find an unknown element of a set of cardinality M with a sequential strategy if at most I of the answers are lies. Obviously, in the case l = 0 [logM] questions are needed. Thus, one more question is necessary if the number of elements is doubled. We show that for every fixed 1 and sufficiently large M, then L-l(2M) less than or equal to L-l(M)+2 and moreover L-l((3)/M-2) less than or equal to L-l(M)+1. These bounds are sharp in infinitely many cases. As a consequence, at most one question more than the information theoretic lower bound is needed to successfully find the unknown number. One of our strategies uses the minimum amount of adaptiveness during the search process. (C) 2003 Elsevier B.V. All rights reserved.
Stichworte
Renyi-Ulam-game; searching with lies
Erscheinungsjahr
2004
Zeitschriftentitel
THEORETICAL COMPUTER SCIENCE
Band
314
Ausgabe
1-2
Seite(n)
45-55
ISSN
0304-3975
Page URI
https://pub.uni-bielefeld.de/record/1608581

Zitieren

Deppe C. Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE. 2004;314(1-2):45-55.
Deppe, C. (2004). Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE, 314(1-2), 45-55. doi:10.1016/j.tcs.2003.10.036
Deppe, C. (2004). Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE 314, 45-55.
Deppe, C., 2004. Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE, 314(1-2), p 45-55.
C. Deppe, “Strategies for the Renyi-Ulam Game with fixed number of lies”, THEORETICAL COMPUTER SCIENCE, vol. 314, 2004, pp. 45-55.
Deppe, C.: Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE. 314, 45-55 (2004).
Deppe, Christian. “Strategies for the Renyi-Ulam Game with fixed number of lies”. THEORETICAL COMPUTER SCIENCE 314.1-2 (2004): 45-55.