Synchronization from deletions through interactive communication

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 β. We offer a deterministic synchronization scheme between nodes A and B that needs O(nβ log 1/β)¹ transmissions to reconstruct X at node B. The rate of our scheme matches the optimal rate for this channel up to a multiplicative constant and the running time of our scheme is O(n⁴β⁶).