Linearly bounded liars, adaptive covering codes, and deterministic random walks
Journal of Combinatorics · 2010 · 1 (3) · 307-333
DOI: 10.4310/joc.2010.v1.n3.a3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorics, 2010. Verfasst von Joshua N. Cooper. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
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}$.
Zitieren
APA
Cooper, J. N. (2010). Linearly bounded liars, adaptive covering codes, and deterministic random walks. Journal of Combinatorics, 1(3), 307-333. https://doi.org/10.4310/joc.2010.v1.n3.a3
Vancouver
Cooper JN. Linearly bounded liars, adaptive covering codes, and deterministic random walks. Journal of Combinatorics. 2010;1(3):307-333. doi:10.4310/joc.2010.v1.n3.a3
BibTeX
@article{Cooper2010,
author = {Cooper, Joshua N.},
title = {Linearly bounded liars, adaptive covering codes, and deterministic random walks},
journal = {Journal of Combinatorics},
year = {2010},
volume = {1},
number = {3},
pages = {307--333},
doi = {10.4310/joc.2010.v1.n3.a3}
}
EUVIMED