Robust Gray Codes Approaching the Optimal Rate
<|reference_start|>Robust Gray Codes Approaching the Optimal Rate: Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code $\mathcal{G}$ so that, given a noisy version of the encoding $\mathcal{G}(j)$ of an integer $j$, one can recover $\hat{j}$ that is close to $j$ (with high probability over the noise). Such codes have found applications in differential privacy.   In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code $\mathcal{G}$ of rate $1 - H_2(p) - \varepsilon$ that is efficiently encodable, and that is robust in the following sense. Supposed that $\mathcal{G}(j)$ is passed through the binary symmetric channel $\text{BSC}_p$ with cross-over probability $p$, to obtain $x$. We present an efficient decoding algorithm that, given $x$, returns an estimate $\hat{j}$ so that $|j - \hat{j}|$ is small with high probability.<|reference_end|>
@article{con2024robust,
    title={Robust Gray Codes Approaching the Optimal Rate},
    author={Roni Con, Dorsa Fathollahi, Ryan Gabrys, Mary Wootters, Eitan Yaakobi},
    journal={arXiv preprint arXiv:2406.17689},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.17689},
    primaryClass={cs.IT cs.DS math.IT}
}