Optimal Quasi-Gray Codes: The Alphabet Matters

A quasi-Gray code of dimension $n$ and length $ell$ over an alphabet $Sigma$ is a sequence of distinct words $w_1,w_2,dots,w_ell$ from $Sigma^n$ such that any two consecutive words differ in at most $c$ coordinates, for some fixed constant $c>0$. In this paper we are interested in the read and write complexity of quasi-Gray codes in the bit-probe model, where we measure the number of symbols read and written in order to transform any word $w_i$ into its successor $w_{i+1}$. We present construction of quasi-Gray codes of dimension $n$ and length $3^n$ over the ternary alphabet ${0,1,2}$ with worst-case read complexity $O(log n)$ and write complexity $2$. This generalizes to arbitrary odd-size alphabets. For the binary alphabet, we present quasi-Gray codes of dimension $n$ and length at least $2^n - 20n$ with worst-case read complexity $6+log n$ and write complexity $2$. This complements a recent result by Raskin [Raskin 17] who shows that any quasi-Gray code over binary alphabet of length $2^n$ has read complexity $Omega(n)$. Our results significantly improve on previously known constructions and for the odd-size alphabets we break the $Omega(n)$ worst-case barrier for space-optimal (non-redundant) quasi-Gray codes with constant number of writes. We obtain our results via a novel application of algebraic tools together with the principles of catalytic computation [Buhrman et al. 14, Ben-Or and Cleve 92, Barrington 89, Coppersmith and Grossman 75].