MO1.R3.3

Improved Construction of Robust Gray Codes

Dorsa Fathollahi, Mary Wootters, Stanford University, United States

Session:
Topics in Modern Coding Theory 1

Track:
2: Modern Coding Theory

Location:
Ypsilon IV-V-VI

Presentation Time:
Mon, 8 Jul, 10:45 - 11:05

Session Chair:
Van Khu Vu, Singapore National University
Abstract
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 $|j - \hat{j}|$ is small with high probability. That work presented a transformation that transforms a binary code $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 $C$ to a robust Gray code with similar robustness guarantees, but with rate that can approach $R/2$. A full version of the paper can be found at https://arxiv.org/abs/2401.15291.
Resources