Improved string reconstruction over insertion-deletion channels
Krishnamurthy Viswanathan, Ram Swaminathan · Symposium on Discrete Algorithms · 2008
Consider a binary string x of length n transmitted m times over a memoryless channel that randomly inserts, deletes and flips bits. We consider the problem of reconstructing x from the collection of m binary strings received at the output of the channel. We present an algorithm for this problem and show that, as n tends to infinity, for almost all transmitted strings, the algorithm is guaranteed to reconstruct the transmitted string with probability 1 - o(1), if the channel's flip probability p qi,qd = O(1/log n), and m = θ(log n). Our algorithm improves on [1] which applies to channels that only delete, and on [2] where qi,qd = O(1/(log n)2). We also show that to reconstruct most strings reliably over any channel with a constant flip probability m = Ω(log n) transmissions are necessary, and therefore our algorithm is efficient in this sense.