2024/01/27 by Dorsa Fathollahi, Mary Wootters, Fathollahi, Dorsa +1
Computer Science · Engineering · #Digital Image Processing Techniques #FOS: Computer and information sciences #Industrial Vision Systems and Defect Detection #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2401.15291
openalex publication_date 2024/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 j so that |j - 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 Ω(R), where the constant in the Ω(⋅) 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.