The trace reconstruction problem asks to reconstruct an unknown n-bit string x given independent random “traces” of x, where a random trace is obtained by first deleting each bit of x independently with some probability (say 0.5), and then outputting the concatenation of the remaining bits of x. A basic question is to determine the number of traces required to reconstruct x (with high probability).  Despite many efforts, this question remains largely open.  In particular, the best known upper bound is exp(~O(n^{1/5})), while the best known lower bound is barely superlinear.

In this talk, I will survey several recent results on this problem and its variants, and highlight its connections to the study of the extremal properties of Littlewood polynomials on complex disks.

Speaker’s website: https://chinholee.github.io/