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.