Q-ary Ulam-Renyi game with weighted constrained lies

Cicalese F, Deppe C, Mundici D (2004)
In: COMPUTING AND COMBINATORICS, PROCEEDINGS. 3106. SPRINGER-VERLAG BERLIN: 82-91.

Conference Paper | Published | English

No fulltext has been uploaded

Author
; ;
Abstract
The Ulam-Renyi game is a classical model for the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number of the answers may be erroneous/mendacious. In the variant considered in this paper, questions with q many possible answers are allowed, with q fixed and known beforehand; further, lies are constrained by a weighted bipartite graph (the "channel"). We provide a tight asymptotic estimate for the number of questions needed to solve the problem. Our results are constructive, and the appropriate searching strategies are actually provided. As an extra bonus, all our strategies use the minimum amount of adaptiveness: they ask a first batch of nonadaptive questions, and then, only depending on the answers to these questions, they ask a second nonadaptive batch.
Publishing Year
ISSN
PUB-ID

Cite this

Cicalese F, Deppe C, Mundici D. Q-ary Ulam-Renyi game with weighted constrained lies. In: COMPUTING AND COMBINATORICS, PROCEEDINGS. Vol 3106. SPRINGER-VERLAG BERLIN; 2004: 82-91.
Cicalese, F., Deppe, C., & Mundici, D. (2004). Q-ary Ulam-Renyi game with weighted constrained lies. COMPUTING AND COMBINATORICS, PROCEEDINGS, 3106, 82-91.
Cicalese, F., Deppe, C., and Mundici, D. (2004). “Q-ary Ulam-Renyi game with weighted constrained lies” in COMPUTING AND COMBINATORICS, PROCEEDINGS, vol. 3106, (SPRINGER-VERLAG BERLIN), 82-91.
Cicalese, F., Deppe, C., & Mundici, D., 2004. Q-ary Ulam-Renyi game with weighted constrained lies. In COMPUTING AND COMBINATORICS, PROCEEDINGS. no.3106 SPRINGER-VERLAG BERLIN, pp. 82-91.
F. Cicalese, C. Deppe, and D. Mundici, “Q-ary Ulam-Renyi game with weighted constrained lies”, COMPUTING AND COMBINATORICS, PROCEEDINGS, vol. 3106, SPRINGER-VERLAG BERLIN, 2004, pp.82-91.
Cicalese, F., Deppe, C., Mundici, D.: Q-ary Ulam-Renyi game with weighted constrained lies. COMPUTING AND COMBINATORICS, PROCEEDINGS. 3106, p. 82-91. SPRINGER-VERLAG BERLIN (2004).
Cicalese, F, Deppe, Christian, and Mundici, D. “Q-ary Ulam-Renyi game with weighted constrained lies”. COMPUTING AND COMBINATORICS, PROCEEDINGS. SPRINGER-VERLAG BERLIN, 2004.Vol. 3106. 82-91.
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