Theory Lunch Seminar November 15, 2017 12:00pm — 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
