Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Trace reconstruction asks: if you repeatedly see randomly deleted versions of an unknown binary string, how many samples do you need to recover the original? Despite a lot of work, the best lower-bounds are polynomial and the best upper-bounds are exponential. Many variants of the model have been introduced in hopes of motivating or revealing new approaches to narrow this gap. Here we discuss perspectives inspired by the circular trace reconstruction model introduced by Narayanan and Ren (ITCS 2021), in which traces undergo a random cyclic shift in addition to random deletions. We introduce several new characterizations of the “low order statistics” of a trace, the most surprising being a Fourier-based analysis that shows that two sparse strings x,y must always differ in some statistic of order at most 6, leading to an n^6 algorithm for the sparse circular setting. These new tools provide promising new avenues to understand trace reconstruction, and construct new data-efficient algorithms.