Next Lecture: Wednesday 18th July, Time: 11:00 -13:00

               Room: Schreiber 209

Speaker: Tsviqa Lakrec (Hebrew University of Jerusalem)

Title: Scenery Reconstruction for a Random Walk on Random Scenery with Adversarial Error Insertion 

Abstract: 
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.