Journal of Combinatorics

Volume 1 (2010)

Number 3

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

Pages: 307 – 333

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

Authors

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

Robert B. Ellis (Department of Applied Mathematics, Illinois Institute of Technology, Chicago, Illinois, U.S.A.)

Abstract

We analyze a deterministic form of the random walk on the integer line called the liar machine, similar to the rotor-router model, finding asymptotically tight pointwise and interval discrepancy bounds versus random walk. This provides an improvement in the best-known winning strategies in the binary symmetric pathological liar game with a linear fraction of responses allowed to be lies. Equivalently, this proves the existence of adaptive 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}$.

Published 1 January 2010