2026-07-24T21:35:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9475 2024-03-06T10:43:50Z ddc:004 open_access

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity Chakraborty, Diptarka Das, Debarati Koucký, Michal Saurabh, Nitin Gray code Space-optimal counter Decision assignment tree Cell probe model 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diptarka Chakraborty and Debarati Das and Michal Koucký and Nitin Saurabh 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.12 urn:nbn:de:0030-drops-94750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode