We study the problem of identifying an initially unknown m-bit number by using yes-no questions when up to a fixed number e of the answers can be erroneous. In the variant we consider here questions are restricted to be the union of up to a fixed number of intervals. For any e≥1 let k_e be the minimum k such that for all sufficiently large m, there exists a strategy matching the information theoretic lowerbound and only using k-interval questions. It is known that k_e=O(e2). However, it has been conjectured that the k_e=Θ(e).This linearity conjecture is supported by the known results for small values of e. For e≤2 we have k_e=e. We extend these results to the case e= 3. We show k_3≤4 improving upon the previously known bound k_3≤10.
|Titolo:||On the multi-interval Ulam-Rényi game: For 3 lies 4 intervals suffice|
Cicalese, Ferdinando (Corresponding)
ROSSI, MASSIMILIANO (Corresponding)
|Data di pubblicazione:||2017|
|Appare nelle tipologie:||04.01 Contributo in atti di convegno|