Theory Lunch Seminar

— 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).

CMU Youtube Theory channel.

Event Website:
http://www.cs.cmu.edu/~theorylunch/20171115.html


Add event to Google
Add event to iCal