EUVIMEDEUVIMED entdecken
Crossref

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

Joshua N. Cooper

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →