TY - GEN

T1 - Approximate Trace Reconstruction

T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021

AU - Davies, Sami

AU - Racz, Miklos Z.

AU - Schiffer, Benjamin G.

AU - Rashtchian, Cyrus

N1 - Funding Information:
ACKNOWLEDGMENTS M.Z.R. was supported in part by NSF grant DMS 1811724 and by a Princeton SEAS Innovation Award. We thank João Ribeiro and Josh Brakensiek for discussions on coded trace reconstruction and the anonymous reviewers for feedback on an earlier version of the paper.
Publisher Copyright:
© 2021 IEEE.

PY - 2021/7/12

Y1 - 2021/7/12

N2 - 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. A full version of this paper is accessible at: https://arxiv.org/abs/2012.06713.pdf

AB - 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. A full version of this paper is accessible at: https://arxiv.org/abs/2012.06713.pdf

UR - http://www.scopus.com/inward/record.url?scp=85112529071&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85112529071&partnerID=8YFLogxK

U2 - 10.1109/ISIT45174.2021.9517926

DO - 10.1109/ISIT45174.2021.9517926

M3 - Conference contribution

AN - SCOPUS:85112529071

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2525

EP - 2530

BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 12 July 2021 through 20 July 2021

ER -