Paper Info
Title
Bounds On The Zero-Error List-Decoding Capacity Of The Q/(Q-1) Channel
Abstract
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, X = {x(1), x(2), ..., x(q)}; when the channel receives an input x is an element of X, it outputs a symbol other than x itself. Let n(m, q, l) be the smallest n for which there is a code C subset of X-n of m elements such that for every list w(1), w(2), ..., w(l+1) of distinct code-words from C, there is a coordinate j is an element of[n] that satisfies {w(1)[j], w(2)[j], ..., w(l+1)[j]} = X. We show that for all constants alpha >= 1, we have n(m, q, alpha q) = exp(Omega(q)) log m.The lower bound obtained by Fredman and Komlos (1984) for perfect hashing implies that n(m, q, q - 1) = exp(Omega(q)) log m; similarly, the lower bound obtained by Korner (1986) for nearly-perfect hashing implies that n(m, q, q) = exp(Omega(q)) log 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) with list size ffq (for every constant alpha >= 1) channel is exponentially small in q.
Year
DOI
Venue
2018
10.1109/isit.2018.8437609
2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
DocType
Volume
Citations 
Conference
abs/1802.08396
0
PageRank 
References 
Authors
0.34
3
2
Name
Order
Citations
PageRank
Siddharth Bhandari103.04
Jaikumar Radhakrishnan2112396.04