Talk
Scenery Reconstruction for a Random Walk on Random Scenery with Adversarial Error Insertion
Talk by Dr. Tsviqa Lakrec
Date: 17.11.21 Time: 17.15 - 18.15 Room: ETH HG G 19.1
Consider a simple random walk on the integers, which are colored at random. Look at the sequence of the first $N$ steps taken and colors of the visited integers. 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? This is the adversarial scenery reconstruction problem. We discuss the history of scenery reconstruction, the connection with ergodic theory, and present the following new theorem on adversarial scenery reconstruction: 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.