14
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# A Deterministic Polynomial-Time Protocol for Synchronizing from Deletions

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

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.

### Most cited references12

• Record: found

### A note on two problems in connexion with graphs

(1959)
Bookmark
• Record: found

### Noiseless coding of correlated information sources

(1973)
Bookmark
• Record: found

### The rate-distortion function for source coding with side information at the decoder

(1976)
Bookmark

### Author and article information

###### Journal
02 July 2012
2013-08-21
1207.0290