TY - GEN
T1 - An Instance-Based Approach to the Trace Reconstruction Problem
AU - Mazooji, Kayvon
AU - Shomorony, Ilan
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - In the trace reconstruction problem, one observes the output of passing a binary string s ∈ {0,1}n through a deletion channel T times and wishes to recover s from the resulting T "traces."Most of the literature has focused on characterizing the hardness of this problem in terms of the number of traces T needed for perfect reconstruction either in the worst case or in the average case (over input sequences s). In this paper, we propose an alternative, instance-based approach to the problem. We define the "Levenshtein difficulty"of a problem instance (s,T) as the probability that the resulting traces do not provide enough information for correct recovery with full certainty. One can then try to characterize, for a specific s, how T needs to scale in order for the Levenshtein difficulty to go to zero, and seek reconstruction algorithms that match this scaling for each s. For a class of binary strings with alternating long runs, we precisely characterize the scaling of T for which the Levenshtein difficulty goes to zero. For this class, we also prove that a simple "Las Vegas algorithm"has an error probability that decays to zero with the same rate as that with which the Levenshtein difficulty tends to zero.
AB - In the trace reconstruction problem, one observes the output of passing a binary string s ∈ {0,1}n through a deletion channel T times and wishes to recover s from the resulting T "traces."Most of the literature has focused on characterizing the hardness of this problem in terms of the number of traces T needed for perfect reconstruction either in the worst case or in the average case (over input sequences s). In this paper, we propose an alternative, instance-based approach to the problem. We define the "Levenshtein difficulty"of a problem instance (s,T) as the probability that the resulting traces do not provide enough information for correct recovery with full certainty. One can then try to characterize, for a specific s, how T needs to scale in order for the Levenshtein difficulty to go to zero, and seek reconstruction algorithms that match this scaling for each s. For a class of binary strings with alternating long runs, we precisely characterize the scaling of T for which the Levenshtein difficulty goes to zero. For this class, we also prove that a simple "Las Vegas algorithm"has an error probability that decays to zero with the same rate as that with which the Levenshtein difficulty tends to zero.
UR - http://www.scopus.com/inward/record.url?scp=85190625665&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85190625665&partnerID=8YFLogxK
U2 - 10.1109/CISS59072.2024.10480213
DO - 10.1109/CISS59072.2024.10480213
M3 - Conference contribution
AN - SCOPUS:85190625665
T3 - 2024 58th Annual Conference on Information Sciences and Systems, CISS 2024
BT - 2024 58th Annual Conference on Information Sciences and Systems, CISS 2024
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 58th Annual Conference on Information Sciences and Systems, CISS 2024
Y2 - 13 March 2024 through 15 March 2024
ER -