All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-S1-T4.2
Paper Title Approximate Trace Reconstruction: Algorithms
Authors Sami Davies, University of Washington, United States; Miklos Z. Racz, Princeton University, United States; Cyrus Rashtchian, University of California at San Diego, United States; Benjamin G. Schiffer, Princeton University, United States
Session D6-S1-T4: Trace Reconstruction
Chaired Session: Monday, 19 July, 22:00 - 22:20
Engagement Session: Monday, 19 July, 22:20 - 22:40
Abstract We introduce approximate trace reconstruction, a relaxed version of the trace reconstruction problem. Here, instead of learning a binary string perfectly from noisy samples, as in the original trace reconstruction problem, the goal is to output a string that is close in edit distance to the original string using few traces. We present several algorithms that can approximately reconstruct strings that belong to certain classes, where the estimate is within n/polylog(n) edit distance and where we only use polylog(n) traces (or sometimes just a single trace). These classes contain strings that require a linear number of traces for exact reconstruction and that are quite different from a typical random string. From a technical point of view, our algorithms approximately reconstruct consecutive substrings of the unknown string by aligning dense regions of traces and using a run of a suitable length to approximate each region.