Three Thresholds for a Liar
Authors:
- 1 March 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 1 (1) , 81-93
Abstract
Motivated by the problem of making correct computations from partly false information, we study a corruption of the classic game “Twenty Questions” in which the player who answers the yes-or-no questions is permitted to lie up to a fixed fraction r of the time. The other player is allowed q arbitrary questions with which to try to determine, with certainty, which of n objects his opponent has in mind; he “wins” if he can always do so, and “wins quickly” if he can do so using only O(log n) questions.It turns out that there is a threshold value for r below which the querier can win quickly, and above which he cannot win at all. However, the threshold value varies according to the precise rules of the game. Our “three thresholds theorem” says that when the answerer is forbidden at any point to have answered more than a fraction r of the questions incorrectly, then the threshold value is r = ½; when the requirement is merely that the total number of lies cannot exceed rq, the threshold is ⅓; and finally if the answerer gets to see all the questions before answering, the threshold drops to ¼.Keywords
This publication has 9 references indexed in Scilit:
- Searching in the presence of linearly bounded errors1991
- ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTSInternational Journal of Foundations of Computer Science, 1990
- Searching with known error probabilityTheoretical Computer Science, 1989
- Solution of Ulam's problem on searching with a lieJournal of Combinatorial Theory, Series A, 1987
- Balancing vectors in the max normCombinatorica, 1986
- Guess a Number-with LyingMathematics Magazine, 1984
- Introduction to Coding Theory1982
- Coping with errors in binary search proceduresJournal of Computer and System Sciences, 1980
- Adventures of a MathematicianPhysics Today, 1976