List Reconstruction Problem with List Size Two
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911715217637376 |
|---|---|
| author | Vu, Binh Wang, Shuche Vu, Van Khu |
| author_facet | Vu, Binh Wang, Shuche Vu, Van Khu |
| contents | The problem of computing the cardinality of the intersection of multiple balls in the Hamming space has attracted a lot of attention recently due to their applications in the list reconstruction problem and information retrieval in Associative Memories. In previous work, most of the results are for the cases where the radii of each ball, $r$ and the distance between the centers of these balls, $k$ are fixed when the length $n$ of each codeword tend to infinity. In this work, we focus on the case where $r = αn$ and $k=βn$ for some constants $α$ and $β$ and compute the maximum asymptotic rate of the cardinality of the intersection of three balls. We provide the maximum asymptotic rate as a function of two parameters $α$ and $β$. We also provide numerical results and compare these results with the intersection of two balls. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23638 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | List Reconstruction Problem with List Size Two Vu, Binh Wang, Shuche Vu, Van Khu Combinatorics Information Theory 94B65 (Primary), 05B40 (Secondary) The problem of computing the cardinality of the intersection of multiple balls in the Hamming space has attracted a lot of attention recently due to their applications in the list reconstruction problem and information retrieval in Associative Memories. In previous work, most of the results are for the cases where the radii of each ball, $r$ and the distance between the centers of these balls, $k$ are fixed when the length $n$ of each codeword tend to infinity. In this work, we focus on the case where $r = αn$ and $k=βn$ for some constants $α$ and $β$ and compute the maximum asymptotic rate of the cardinality of the intersection of three balls. We provide the maximum asymptotic rate as a function of two parameters $α$ and $β$. We also provide numerical results and compare these results with the intersection of two balls. |
| title | List Reconstruction Problem with List Size Two |
| topic | Combinatorics Information Theory 94B65 (Primary), 05B40 (Secondary) |
| url | https://arxiv.org/abs/2605.23638 |