| Paper ID | D6-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.
|
