In this talk 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, polynomial-time synchronization scheme between nodes A and B with number of transmissions that is optimal within a small multiplicative factor of the optimal number of transmissions.
The main novelty in our work is to reduce the synchronization problem into a graph theoretic problem where decoding the received sequence corresponds to finding a shortest path between two vertices of a specifically designed graph.