An Instance-Based Approach to the Trace Reconstruction Problem

Kayvon Mazooji, Ilan Shomorony

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2024 58th Annual Conference on Information Sciences and Systems, CISS 2024
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350369298
DOIs
StatePublished - 2024
Event58th Annual Conference on Information Sciences and Systems, CISS 2024 - Princeton, United States
Duration: Mar 13 2024Mar 15 2024

Publication series

Name2024 58th Annual Conference on Information Sciences and Systems, CISS 2024

Conference

Conference58th Annual Conference on Information Sciences and Systems, CISS 2024
Country/TerritoryUnited States
CityPrinceton
Period3/13/243/15/24

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Safety, Risk, Reliability and Quality
  • Control and Optimization
  • Modeling and Simulation
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'An Instance-Based Approach to the Trace Reconstruction Problem'. Together they form a unique fingerprint.

Cite this