Theory Lunch Seminar

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

CMU Youtube Theory channel.

Event Website:

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

For More Information, Contact:

nresch@cs.cmu.edu

Keywords:

Seminar Series