Please note: This seminar will take place in DC 1304 and online.
Paul Valiant, Professor
Department of Computer Science, Purdue University
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.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.