Reconstruction of Mixed-Up Messages

A famous problem in probability, information theory and theoretical computer science is the following: A long message over a finite alphabet is sent via an information channel. Now suppose that the message that arrives at the receiver is not the original one, but a randomly corrupted version. Suppose further that the receiver knows the random mechanism corrupting the message. Now the question is: Can the receiver recover the original message?

To formulate this mathematically, suppose that to each integer number a letter from the finite alphabet is assigned and a simple random walk runs on the integers. At each time t it registers the letter it observes at its current position. This produces a new random sequence of letters.

Now the question is: Can the original message be reconstructed with probability one from this newly created random sequence? In general, it cannot, but under appropriate restrictions, it can. Lindenstrauss (1999) showed that there are messages which cannot be reconstructed.

However, it is known that almost surely a "typical" message, drawn at random according to a given distribution, can be reconstructed (possibly up to shift and/or reflection).

A natural extension of this problem is to consider it in higher dimensions. In the proposed project we want focus dimension two, which is a critical case, and understand under which conditions a finite piece of the message can be reconstructed in polynomial time (polynomial in relation to the size of the piece reconstructed). In addition, we aim to provide a concrete algorithm that achieves this reconstruction without using supercomputers and quantum computers.