Improved Construction of Robust Gray Codes
Dorsa Fathollahi, Mary K. Wootters · 2024
A robust Gray code, formally introduced by (Lolck and Pagh, SODA 2024), is a Gray code that additionally has the property that, given a noisy version of the encoding of an integer$j$, it is possible to reconstruct$\hat{j}$so that$\vert j-\hat{j}\vert$is small with high probability. That work presented a transformation that transforms a binary code$\mathcal{C}$of rate$R$to a robust Gray code with rate$\Omega(R)$, where the constant in the$\Omega(\cdot)$can be at most 1/4. We improve upon their construction by presenting a transformation from a (linear) binary code$\mathcal{C}$to a robust Gray code with similar robustness guarantees, but with rate that can approach$R/2$. A full version of this paper can be found in [1].