Chakraborty, Diptarka ;
Das, Debarati ;
Koucký, Michal ;
Saurabh, Nitin
SpaceOptimal QuasiGray Codes with Logarithmic Read Complexity
Abstract
A quasiGray code of dimension n and length l over an alphabet Sigma is a sequence of distinct words w_1,w_2,...,w_l 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 quasiGray codes in the bitprobe 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 quasiGray codes of dimension n and length 3^n over the ternary alphabet {0,1,2} with worstcase read complexity O(log n) and write complexity 2. This generalizes to arbitrary oddsize alphabets. For the binary alphabet, we present quasiGray codes of dimension n and length at least 2^n  20n with worstcase read complexity 6+log n and write complexity 2. This complements a recent result by Raskin [Raskin '17] who shows that any quasiGray code over binary alphabet of length 2^n has read complexity Omega(n).
Our results significantly improve on previously known constructions and for the oddsize alphabets we break the Omega(n) worstcase barrier for spaceoptimal (nonredundant) quasiGray 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, BenOr and Cleve '92, Barrington '89, Coppersmith and Grossman '75].
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2018:9475,
author = {Diptarka Chakraborty and Debarati Das and Michal Kouck{\'y} and Nitin Saurabh},
title = {{SpaceOptimal QuasiGray Codes with Logarithmic Read Complexity}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {12:112:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9475},
URN = {urn:nbn:de:0030drops94750},
doi = {10.4230/LIPIcs.ESA.2018.12},
annote = {Keywords: Gray code, Spaceoptimal counter, Decision assignment tree, Cell probe model}
}
2018
Keywords: 

Gray code, Spaceoptimal counter, Decision assignment tree, Cell probe model 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 