TY - GEN
T1 - The interval liar game
AU - Doerr, Benjamin
AU - Lengler, Johannes
AU - Steurer, David
PY - 2006/12/1
Y1 - 2006/12/1
N2 - 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 "burst error model", in which 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 (for big n) Paul needs roughly logn+loglogn+k rounds to determine the number, which is only k more than the case of just one single lie.
AB - 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 "burst error model", in which 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 (for big n) Paul needs roughly logn+loglogn+k rounds to determine the number, which is only k more than the case of just one single lie.
U2 - 10.1007/11940128_33
DO - 10.1007/11940128_33
M3 - Conference contribution
AN - SCOPUS:77249171808
SN - 3540496947
SN - 9783540496946
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 318
EP - 327
BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
T2 - 17th International Symposium on Algorithms and Computation, ISAAC 2006
Y2 - 18 December 2006 through 20 December 2006
ER -