Can I read Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks on EtoBox?

Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks by Cooper, Joshua N.; Ellis, Robert B. is a scholarly article available to read on EtoBox.

What is Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks about?

We analyze a deterministic form of the random walk on the integer line called the {\em 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}$.

Author

Cooper, Joshua N.; Ellis, Robert B.

Published

2009

Language

EN