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.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Cicalese, F; Deppe, ChristianUniBi; Mundici, D
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
2004
Titel des Konferenzbandes
COMPUTING AND COMBINATORICS, PROCEEDINGS
Band
3106
Seite(n)
82-91
ISSN
0302-9743
Page URI
https://pub.uni-bielefeld.de/record/1606534

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.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar