Coding Schemes for Document Exchange under Multiple Substring Edits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912849734926336 |
|---|---|
| author | Narayanan, Hrishi Ramkumar, Vinayak Bitar, Rawad Wachter-Zeh, Antonia |
| author_facet | Narayanan, Hrishi Ramkumar, Vinayak Bitar, Rawad Wachter-Zeh, Antonia |
| contents | We study the document exchange problem under multiple substring edits. A substring edit in a string $\mathbf{x}$ occurs when a substring $\mathbf{u}$ of $\mathbf{x}$ is replaced by an arbitrary string $\mathbf{v}$. The lengths of $\mathbf{u}$ and $\mathbf{v}$ are bounded from above by a fixed constant. Let $\mathbf{x}$ and $\mathbf{y}$ be two binary strings that differ by multiple substring edits. The aim of document exchange schemes is to construct an encoding of $\mathbf{x}$ with small length such that $\mathbf{x}$ can be recovered using $\mathbf{y}$ and the encoding. We construct a low-complexity document exchange scheme with encoding length of $4t\log n+o(\log n)$ bits, where $n$ is the length of the string $\mathbf{x}$. The best known scheme achieves an encoding length of $4t \log n+O(\log\log n)$ bits, but at a much higher computational complexity. Then, we investigate the average length of valid encodings for document exchange schemes with uniform strings $\mathbf{x}$ and develop a scheme with an expected encoding length of $(4t-1) \log n+o(\log n)$ bits. In this setting, prior works have only constructed schemes for a single substring edit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18441 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Coding Schemes for Document Exchange under Multiple Substring Edits Narayanan, Hrishi Ramkumar, Vinayak Bitar, Rawad Wachter-Zeh, Antonia Information Theory We study the document exchange problem under multiple substring edits. A substring edit in a string $\mathbf{x}$ occurs when a substring $\mathbf{u}$ of $\mathbf{x}$ is replaced by an arbitrary string $\mathbf{v}$. The lengths of $\mathbf{u}$ and $\mathbf{v}$ are bounded from above by a fixed constant. Let $\mathbf{x}$ and $\mathbf{y}$ be two binary strings that differ by multiple substring edits. The aim of document exchange schemes is to construct an encoding of $\mathbf{x}$ with small length such that $\mathbf{x}$ can be recovered using $\mathbf{y}$ and the encoding. We construct a low-complexity document exchange scheme with encoding length of $4t\log n+o(\log n)$ bits, where $n$ is the length of the string $\mathbf{x}$. The best known scheme achieves an encoding length of $4t \log n+O(\log\log n)$ bits, but at a much higher computational complexity. Then, we investigate the average length of valid encodings for document exchange schemes with uniform strings $\mathbf{x}$ and develop a scheme with an expected encoding length of $(4t-1) \log n+o(\log n)$ bits. In this setting, prior works have only constructed schemes for a single substring edit. |
| title | Coding Schemes for Document Exchange under Multiple Substring Edits |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.18441 |