Perfect, minimally adaptive, error-correcting searching strategies
Ferdinando Cicalese, Daniele Mundici, Ugo Vaccaro · 2002
Let q/sub e/(m) be the smallest integer q satisfying Berlekamp's bound /spl Sigma//sub i=0//sup e/(/sub i//sup q/)/spl les/2/sup q-m/. We prove that for any fixed e/spl ges/1 and all sufficiently large m there is a binary searching strategy to guess a number x/spl isin/{0,...,2/sup m/-1} in spite of up to e lies in the answers, which uses exactly q/sub e/(m) questions and adaptiveness only once. The strategy goes through a first batch of m non-adaptive questions asking for the bits of the binary expansion of x and then, only depending on the answers to these questions, a second batch of q/sub e/(m)-m non-adaptive questions.