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 - 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 -