TY - GEN
T1 - Substring Density Estimation from Traces
AU - Mazooji, Kayvon
AU - Shomorony, Ilan
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - In the trace reconstruction problem, one seeks to reconstruct a binary string s from a collection of traces, each of which is obtained by passing s through a deletion channel. It is known that exp(Õ(n1/5)) traces suffice to reconstruct any length-n string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a "density map"that indicates the locations of each length-k substring throughout s. We show that ?-2 • poly(n) traces suffice to recover the density map with error at most ?. As a result, when restricted to a set of source strings whose minimum "density map distance"is at least 1/poly(n), the trace reconstruction problem can be solved with polynomially many traces.
AB - In the trace reconstruction problem, one seeks to reconstruct a binary string s from a collection of traces, each of which is obtained by passing s through a deletion channel. It is known that exp(Õ(n1/5)) traces suffice to reconstruct any length-n string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a "density map"that indicates the locations of each length-k substring throughout s. We show that ?-2 • poly(n) traces suffice to recover the density map with error at most ?. As a result, when restricted to a set of source strings whose minimum "density map distance"is at least 1/poly(n), the trace reconstruction problem can be solved with polynomially many traces.
UR - http://www.scopus.com/inward/record.url?scp=85171462274&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85171462274&partnerID=8YFLogxK
U2 - 10.1109/ISIT54713.2023.10206758
DO - 10.1109/ISIT54713.2023.10206758
M3 - Conference contribution
AN - SCOPUS:85171462274
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 803
EP - 808
BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023
Y2 - 25 June 2023 through 30 June 2023
ER -