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

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

Journal Article | Published | English

No fulltext has been uploaded

Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

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.
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.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar