Date:
Tue, 08/05/201812:00-13:00
Location:
Manchester 209
Consider a simple random walk on $\mathbb{Z}$ with a random coloring of $\mathbb{Z}$.
Look at the sequence of the first $N$ steps taken and colors of the visited locations.
From it, you can deduce the coloring of approximately $\sqrt{N}$ integers.
Suppose an adversary may change $\delta N$ entries in that sequence. What can be deduced now?
We show that for any $\theta<0.5,p>0$, there are $N_{0},\delta_{0}$
such that if $N>N_{0}$ and $\delta<\delta_{0}$ then with probability $>1-p$ we can reconstruct
the coloring of $>N^{\theta}$ integers.
Look at the sequence of the first $N$ steps taken and colors of the visited locations.
From it, you can deduce the coloring of approximately $\sqrt{N}$ integers.
Suppose an adversary may change $\delta N$ entries in that sequence. What can be deduced now?
We show that for any $\theta<0.5,p>0$, there are $N_{0},\delta_{0}$
such that if $N>N_{0}$ and $\delta<\delta_{0}$ then with probability $>1-p$ we can reconstruct
the coloring of $>N^{\theta}$ integers.