On the trace reconstruction problem.

par Guillaume Aubrun

jeudi 20 févr. 2020, 16:00 → 17:30 Europe/Paris

435 UMPA

we present the following problem: an unknown bit string x in {0,1}^n is observed through the deletion channel, which deletes each bit with probability 1/2, resulting in a shorter string. How many observations are needed in order to be able to reconstruct an arbitrary x with probability 0.999 ? (after Nazarov-Peres arxiv:1612.03599 and several other papers).