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.
On the multi-interval Ulam-Rényi game: For 3 lies 4 intervals suffice
Cicalese, F.
;Rossi, M.
2017-01-01
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
