License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.12
URN: urn:nbn:de:0030-drops-94750
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9475/
Chakraborty, Diptarka ;
Das, Debarati ;
Koucký, Michal ;
Saurabh, Nitin
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity
Abstract
A quasi-Gray 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 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. This complements a recent result by Raskin [Raskin '17] who shows that any quasi-Gray code over binary alphabet of length 2^n has read complexity Omega(n).
Our results significantly improve on previously known constructions and for the odd-size alphabets we break the Omega(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].
BibTeX - Entry
@InProceedings{chakraborty_et_al:LIPIcs:2018:9475,
author = {Diptarka Chakraborty and Debarati Das and Michal Kouck{\'y} and Nitin Saurabh},
title = {{Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9475},
URN = {urn:nbn:de:0030-drops-94750},
doi = {10.4230/LIPIcs.ESA.2018.12},
annote = {Keywords: Gray code, Space-optimal counter, Decision assignment tree, Cell probe model}
}
|
Keywords: |
|
Gray code, Space-optimal counter, Decision assignment tree, Cell probe model |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
