- Series
- Combinatorics Seminar
- Time
- Thursday, May 21, 2009 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Joshua Cooper – Department of Mathematics, University of South Carolina
- Organizer
- Prasad Tetali
We consider the Ulam "liar" and "pathological liar" games, natural and well-studied variants of "20 questions" in which the adversarial respondent is permitted to lie some fraction of the time. We give an improved upper bound for the optimal strategy (aka minimum-size covering code), coming within a triply iterated log factor of the so-called "sphere covering" lower bound. The approach is twofold: (1) use a greedy-type strategy until the game is nearly over, then (2) switch to applying the "liar machine" to the remaining Berlekamp position vector. The liar machine is a deterministic (countable) automaton which we show to be very close in behavior to a simple random walk, and this resemblance translates into a nearly optimal strategy for the pathological liar game.