IFML Seminar: 10/23/26 - Quasipolynomial Trace Reconstruction

Abstract: Trace reconstruction asks: if you repeatedly see randomly deleted versions of an unknown binary string x, how many samples do you need to recover x? This has been one of the defining challenges in the area of "data efficient algorithms". Until this summer, despite a lot of work, the best lower-bounds were polynomial and the best upper-bounds were exponential. We show the first quasipolynomial trace reconstruction algorithm, requiring n^(polylog(n)) samples, adapting ideas from our prior ITCS paper on the circular trace reconstruction model. Our work exposes interesting new connections to the Blum-Luby-Rubinfeld 3-point linearity test, and the multiple reference alignment problem - subject of the 2017 Nobel Prize in Chemistry. Recently, OpenAI's October 6 preprint release included 3 works following up on our result: an almost-matching n^log log n lower bound, and two algorithmic results that improve constants and improve the run-time to match our sample complexity bounds. 

This is joint work with Arnav Burudgunte and Hongao Wang.

Bio: Dr. Paul Valiant is an Associate Professor of Computer Science at Purdue University, since 2021. His research interests span algorithms and complexity, machine learning, and statistics, with a particular focus on sublinear algorithms, statistical inference, and lower bounds. He is the recipient of a Sloan Research Fellowship, a Test of Time award at TCC, and a Machtey Best Student Paper award at FOCS. He received his Ph.D. from MIT and held an NSF Mathematical Sciences Postdoctoral Fellowship at UC Berkeley.

Zoom link: https://utexas.zoom.us/j/89110047398