hide
Free keywords:
-
Abstract:
We regard the problem of communication in the presence of faulty
transmissions. In contrast to the classical works in this area, we assume some
structure on the times when the faults occur. More realistic seems the model
that
all faults occur in some small time interval.
Like previous work, our problem can best be modelled as a two-player perfect
information game, in which one player (“Paul”) has to guess a number x from
{1, . . . , n} using Yes/No-questions, which the second player (“Carole”) has to
answer truthfully apart from few lies. In our setting, all lies have to be in a
consecutive
set of k rounds.
We show that Paul needs roughly log n + log log n + k rounds to determine the
number, which is only k more than the case of just one single lie.
