Talks - Spring 2018

Diptarka Chakraborty

Title

Speaker

Date

Time

Venue

Abstract

Optimal Quasi-Gray Codes: Does the Alphabet Matter?

Diptarka Chakraborty

17, Jan 2018

5-6pm

KD101

A quasi-Gray code of dimension $n$ and length $\ell$ over an alphabet $\Sigma$ is a sequence of distinct words $w_1,w_2,\dots,w_\ell$ 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$.

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. We also establish certain limits of our technique in the binary case.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator