Space-optimal quasi-Gray codes with logarithmic read complexity

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


A quasi-Gray code of dimension n and length ℓ over an alphabet Σ is a sequence of distinct words w1, w2,⋯, 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 wi into its successor wi+1. We present construction of quasi-Gray codes of dimension n and length 3n over the ternary alphabet {0,1, 2} with worst-case read complexity O(logn) 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 2n - 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 2n has read complexity Ω(n). 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].

Original languageEnglish (US)
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770811
StatePublished - Aug 1 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference26th European Symposium on Algorithms, ESA 2018

All Science Journal Classification (ASJC) codes

  • Software

Cite this