On the Multi-Interval Ulam-Rényi Game: for 3 lies 4 intervals suffice

Ferdinando Cicalese, Massimiliano Rossi

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 c…