2024/06/25 by Con, Roni, Fathollahi, Dorsa, Gabrys, Ryan +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2406.17689
Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code G so that, given a noisy version of the encoding G(j) of an integer j, one can recover 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 G of rate 1 - H2(p) - ε that is efficiently encodable, and that is robust in the following sense. Supposed that G(j) is passed through the binary symmetric channel BSCp with cross-over probability p, to obtain x. We present an efficient decoding algorithm that, given x, returns an estimate j so that |j - j| is small with high probability.