Journal of Combinatorics

Volume 1 (2010)

Number 3

Linearly bounded liars, adaptive covering codes, and deterministic random walks

Pages: 307 – 333

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n3.a3

Author

Joshua N. Cooper (Department of Mathematics, University of South Carolina, Columbia, South Carolina, U.S.A.)

Abstract

We analyze a deterministic form of the random walk on theinteger line called the {\em liar machine}, similar to therotor-router model, finding asymptotically tight pointwise and interval discrepancybounds versus random walk. This provides an improvement inthe best-known winning strategies in the binary symmetricpathological liar game with a linear fraction of responsesallowed to be lies. Equivalently, this proves the existence ofadaptive binary block covering codes with block length $n$,covering radius $\leq fn$ for $f\in(0,1/2)$, and cardinality$O(\sqrt{\log \log n}/(1-2f))$ times the sphere bound$2^n/\binom{n}{\leq \lfloor fn\rfloor}$.

Full Text (PDF format)