Robust Gray Codes Approaching The Optimal Rate

Counting queries are typically made differentially private by adding Laplace noise, but this can be resource-intensive. Robust Gray codes, introduced by Lolck and Pagh (SODA 2024), offer an alternative by achieving differential privacy through binary bitflips. 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). In this talk, I will present near-optimal constructions of robust Gray codes with a rate of 1−H2 (p)−ϵ. I will discuss the motivation behind these codes and provide intuition on their construction.