Capacity-Achieving Gray Codes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914848764329984 |
|---|---|
| author | Guruswami, Venkatesan Wang, Hsin-Po |
| author_facet | Guruswami, Venkatesan Wang, Hsin-Po |
| contents | To ensure differential privacy, one can reveal an integer fuzzily in two ways: (a) add some Laplace noise to the integer, or (b) encode the integer as a binary string and add iid BSC noise. The former is simple and natural while the latter is flexible and affordable, especially when one wants to reveal a sparse vector of integers. In this paper, we propose an implementation of (b) that achieves the capacity of the BSC with positive error exponents. Our implementation adds error-correcting functionality to Gray codes by mimicking how software updates back up the files that are getting updated ("coded Gray code"). In contrast, the old implementation of (b) interpolates between codewords of a black-box error-correcting code ("Grayed code"). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17669 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Capacity-Achieving Gray Codes Guruswami, Venkatesan Wang, Hsin-Po Information Theory Data Structures and Algorithms To ensure differential privacy, one can reveal an integer fuzzily in two ways: (a) add some Laplace noise to the integer, or (b) encode the integer as a binary string and add iid BSC noise. The former is simple and natural while the latter is flexible and affordable, especially when one wants to reveal a sparse vector of integers. In this paper, we propose an implementation of (b) that achieves the capacity of the BSC with positive error exponents. Our implementation adds error-correcting functionality to Gray codes by mimicking how software updates back up the files that are getting updated ("coded Gray code"). In contrast, the old implementation of (b) interpolates between codewords of a black-box error-correcting code ("Grayed code"). |
| title | Capacity-Achieving Gray Codes |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.17669 |