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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {G}$ </tex-math></inline-formula> so that, given a noisy version of the encoding <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {G}(j)$ </tex-math></inline-formula> of an integer j, one can recover <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {j}$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {G}$ </tex-math></inline-formula> of rate <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1 - H_{2}(p) - \varepsilon $ </tex-math></inline-formula> that is efficiently encodable, and that is robust in the following sense. Supposed that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {G}(j)$ </tex-math></inline-formula> is passed through the binary symmetric channel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\text {BSC}}_{p}$ </tex-math></inline-formula> with cross-over probability p, to obtain x. We present an efficient decoding algorithm that, given x, returns an estimate <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {j}$ </tex-math></inline-formula> so that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$| j - \hat {j}|$ </tex-math></inline-formula> is small with high probability.