Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Optimal Quasi-Gray Codes: Does the Alphabet matter?
Speaker:Nitin Saurabh
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 1 February 2018
Duration:30 Minutes
Building:E1 4
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.

Here 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.

These constructions improve over the previously known constructions and matches the \Omega(\log n) lower bound up to a constant factor.

This is a joint work with Diptarka Chakraborty, Debarati Das and Michal Koucky.

Name(s):Nitin Saurabh
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Nitin Saurabh, 01/25/2018 03:52 PM
Last modified:
Uwe Brahm/MPII/DE, 02/01/2018 04:01 AM
  • Nitin Saurabh, 01/29/2018 12:37 PM
  • Nitin Saurabh, 01/25/2018 03:52 PM -- Created document.