2017/08/29 by Cicalese, Ferdinando, Rossi, Massimiliano
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.08738
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 ke be the minimum k such that for all sufficiently large m, there exists a strategy matching the information theoretic lower bound and only using k-interval questions. It is known that ke = O(e2). However, it has been conjectured that the ke = Θ(e). This linearity conjecture is supported by the known results for small values of e. For e≤2 we have ke = e. We extend these results to the case e=3. We show k3 ≤ 4 improving upon the previously known bound k3 ≤ 10.