Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks

Details Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks

2009-08-31

arxiv.org/abs/0909.0029v1

Mathematics

Combinatorics

23 pages

Scientific paper

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}$.

Affiliated with

Also associated with

No associations

Rating

Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-287746