Optimal Quasi-Gray Codes: Does the Alphabet matter?

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.

Here 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.

These constructions improve over the previously known constructions and matches the \Omega(\log n) lower bound up to a constant factor.

This is a joint work with Diptarka Chakraborty, Debarati Das and Michal Koucky.