Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions

Ramji Venkataramanan, Vasuki Narasimha Swamy, Kannan Ramchandran

Consider two remote nodes having binary sequences $X$ and $Y$, respectively. $Y$ is an edited version of $X$, where the editing involves random deletions, insertions, and substit…