Bounds on the Zero-Error List-Decoding Capacity of the q/(q-1) Channel
share
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,..., x_q}; when the channel receives an input x ∈ Q, it outputs a symbol other than x itself. Let n(m,q,ℓ) be the smallest n for which there is a code C ⊆ Q^n of m elements such that for every list w_1, w_2, ..., w_ℓ+1 of distinct code-words from C, there is a coordinate j ∈ [n] that satisfies {w_1[j], w_2[j], ..., w_ℓ+1[j]} = Q. We show that for ϵ<1/6, for all large q and large enough m, n(m,q, ϵ qq) ≥Ω((q^1-6ϵ/8)_2m). The lower bound obtained by Fredman and Komlós (1984) for perfect hashing implies that n(m,q,q-1) = (Ω(q)) _2 m; similarly, the lower bound obtained by Körner (1986) for nearly-perfect hashing implies that n(m,q,q) = (Ω(q)) _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 ϵ q for ϵ<1/6 is (Ω(q^1-6ϵ)). 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.
READ FULL TEXT