Bounds on the Zero-Error List-Decoding Capacity of the $q/(q-1)$ Channel

We consider the problem of determining the zero-error list-decoding capacity of the $q/(q-1)$ channel studied by Elias (1988). The $q/(q-1)$ channel has input and output alphabet consisting of $q$ symbols, say, $Q = {x_1,x_2,ldots, x_q}$; when the channel receives an input $x in Q$, it outputs a symbol other than $x$ itself. Let $n(m,q,ell)$ be the smallest $n$ for which there is a code $C subseteq Q^n$ of $m$ elements such that for every list $w_1, w_2, ldots, w_{ell+1}$ of distinct code-words from $C$, there is a coordinate $j in [n]$ that satisfies ${w_1[j], w_2[j], ldots, w_{ell+1}[j]} = Q$. We show that for $epsilon<1/6$, for all large $q$ and large enough $m$, $n(m,q, epsilon qln{q}) geq Omega(exp{(q^{1-6epsilon}/8)}log_2{m})$. The lower bound obtained by Fredman and Koml{o}s (1984) for perfect hashing implies that $n(m,q,q-1) = exp(Omega(q)) log_2 m$; similarly, the lower bound obtained by K{o}rner (1986) for nearly-perfect hashing implies that $n(m,q,q) = exp(Omega(q)) log_2 m$. These results show that the zero-error list-decoding capacity of the $q/(q-1)$ channel with lists of size at most $q$ is exponentially small. Extending these bounds, Chakraborty et al. (2006) showed that the capacity remains exponentially small even if the list size is allowed to be as large as $1.58q$. Our result implies that the zero-error list-decoding capacity of the $q/(q-1)$ channel with list size $epsilon q$ for $epsilon<1/6$ is $exp{(Omega(q^{1-6epsilon}))}$. This resolves the conjecture raised by Chakraborty et al. (2006) about the zero-error list-decoding capcity of the $q/(q-1)$ channel at larger list sizes.