Optimal Quasi-Gray Codes: Does the Alphabet Matter?
share
A quasi-Gray code of dimension n and length ℓ over an alphabet Σ is a sequence of distinct words w_1,w_2,...,w_ℓ from Σ^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( 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+ n and write complexity 2. Our results significantly improve on previously known constructions and for the odd-size alphabets we break the Ω(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]. We also establish certain limits of our technique in the binary case. Although our techniques cannot give space-optimal quasi-Gray codes with small read complexity over the binary alphabet, our results strongly indicate that such codes do exist.
READ FULL TEXT