Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2411.18765 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913590003367936 |
|---|---|
| author | Aamand, Anders Liu, Allen Narayanan, Shyam |
| author_facet | Aamand, Anders Liu, Allen Narayanan, Shyam |
| contents | In the trace reconstruction problem our goal is to learn an unknown string $x\in \{0,1\}^n$ given independent traces of $x$. A trace is obtained by independently deleting each bit of $x$ with some probability $δ$ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability $δ$ is constant. The best known upper bound and lower bounds are respectively $\exp(\tilde O(n^{1/5}))$ and $\tilde Ω(n^{3/2})$ both by Chase [Cha21b,Cha21a]. Our main result is that if the string $x$ is mildly separated, meaning that the number of zeros between any two ones in $x$ is at least polylog$n$, and if $δ$ is a sufficiently small constant, then the trace reconstruction problem can be solved with $O(n \log n)$ traces and in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18765 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Trace Reconstruction for Mildly Separated Strings Aamand, Anders Liu, Allen Narayanan, Shyam Data Structures and Algorithms In the trace reconstruction problem our goal is to learn an unknown string $x\in \{0,1\}^n$ given independent traces of $x$. A trace is obtained by independently deleting each bit of $x$ with some probability $δ$ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability $δ$ is constant. The best known upper bound and lower bounds are respectively $\exp(\tilde O(n^{1/5}))$ and $\tilde Ω(n^{3/2})$ both by Chase [Cha21b,Cha21a]. Our main result is that if the string $x$ is mildly separated, meaning that the number of zeros between any two ones in $x$ is at least polylog$n$, and if $δ$ is a sufficiently small constant, then the trace reconstruction problem can be solved with $O(n \log n)$ traces and in polynomial time. |
| title | Near-Optimal Trace Reconstruction for Mildly Separated Strings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.18765 |