Dynamics Seminar: Tsviqa Lakrec (Huji)

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.

Date: 

Tue, 08/05/2018 - 12:00 to 13:00

Location: 

Manchester 209