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.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Autor
; ;
Abstract / Bemerkung
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.
Erscheinungsjahr
Titel des Konferenzbandes
COMPUTING AND COMBINATORICS, PROCEEDINGS
Band
3106
Seite
82-91
ISSN
PUB-ID

Zitieren

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. SPRINGER-VERLAG BERLIN.
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.