The Ulam-Rényi 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.

Q-ary Ulam-Renyi game with weighted constrained lies / D.MUNDICI; F.CICALESE; C.DEPPE. - STAMPA. - (2004), pp. 82-91. [10.1007/978-3-540-27798-9_11]

Q-ary Ulam-Renyi game with weighted constrained lies

MUNDICI, DANIELE;
2004

Abstract

The Ulam-Rényi 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.
10th International Computing and Combinatorics Conference (COCOON 2004)
82
91
D.MUNDICI; F.CICALESE; C.DEPPE
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/315053
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact