### Wednesday, November 15, 2017 - 12:00pm to 1:00pm

### Location:

8102 Gates Hillman Centers### Speaker:

RYAN O'DONNELL, Professor http://www.cs.cmu.edu/~odonnell/### Optimal Mean-based Algorithms for Trace Reconstruction

There is an unknown n-bit string x. A "trace" is a random substring of x formed by deleting each bit with probability (say) 1/2. Suppose an algorithm has access to independent traces of x. How many does it need to reconstruct x? The previous best method needed about exp(n^{1/2}) traces. We give a simple "mean-based" algorithm that uses about exp(n^{1/3}) traces (and time). We also show that any algorithm working in the restricted "mean-based" framework requires exp(n^{1/3}) traces. The main tool in our work is elementary complex analysis.

*Joint work with Anindya De (Northwestern) and Rocco Servedio (Columbia).*