A Deterministic Polynomial-Time Protocol for Synchronizing from Deletions

In this paper, we consider a synchronization problem between nodes \(A\) and \(B\) that are connected through a two--way communication channel. {Node \(A\)} contains a binary file \(X\) of length \(n\) and {node \(B\)} contains a binary file \(Y\) that is generated by randomly deleting bits from \(X\), by a small deletion rate \(\beta\). The location of deleted bits is not known to either node \(A\) or node \(B\). We offer a deterministic synchronization scheme between nodes \(A\) and \(B\) that needs a total of \(O(n\beta\log \frac{1}{\beta})\) transmitted bits and reconstructs \(X\) at node \(B\) with probability of error that is exponentially low in the size of \(X\). Orderwise, the rate of our scheme matches the optimal rate for this channel.