2018
May
08

# Dynamics Seminar: Tsviqa Lakrec (Huji)

12:00pm to 1:00pm

## 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

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