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:

Keywords:

Seminar Series

Undergraduate Programs

The admissions process for each undergraduate major varies from program to program, but admissions for our main bachelor of science in computer science are handled through Carnegie Mellon's central Office of Undergraduate Admission. Learn more on our Undergraduate Admissions page.

Master's Programs

The Computer Science Department offers a main M.S. in Computer Science, and applications for that program are submitted online by mid-December for fall admission the following year. Other master's programs available to CSD students have their own admissions processes. Learn more about our admissions requirements and processes here.

Doctoral Programs

The Ph.D. in CS program uses the School of Computer Science online application for admissions. Applications are due in December for admittance the following fall. Students cannot begin in the spring. For more on how to apply, visit our Doctoral Admissions page.

Apply

Faculty Positions

The 2018-2019 application period for the Computer Science Department (CSD) at Carnegie Mellon University is open from September 1 through December 3, 2018.

Each year we seek candidates who have demonstrated commitment to excellence and leadership in undergraduate and graduate teaching, research, and/or service toward building an equitable and diverse scholarly environment.

Additional information can be found on our Faculty Hiring page.