Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Optimal Quasi-Gray Codes: The Alphabet Matters   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$. 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].

33
The categories of this paper are: plasm-ph
6
The categories of this paper are: astro-ph
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess
30
The categories of this paper are: q-alg
17
The categories of this paper are: q-fin
31
The categories of this paper are: ao-sci
21
The categories of this paper are: adap-org
3
The categories of this paper are: physics
29
The categories of this paper are: funct-an
8
The categories of this paper are: hep-ex
24
The categories of this paper are: dg-ga
7
The categories of this paper are: hep-th
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
12
The categories of this paper are: nucl-th