English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of determining the zero-error list-decoding capacityof the $q/(q-1)$ channel studied by Elias (1988). The $q/(q-1)$ channel hasinput 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$, itoutputs 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 everylist $w_1, w_2, \ldots, w_{\ell+1}$ of distinct code-words from $C$, there is acoordinate $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$ andlarge enough $m$, $n(m,q, \epsilon q\ln{q}) \geq\Omega(\exp{(q^{1-6\epsilon}/8)}\log_2{m})$. The lower bound obtained byFredman 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 capacityremains 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-6\epsilon}))}$. This resolves the conjecture raised byChakraborty et al. (2006) about the zero-error list-decoding capcity of the$q/(q-1)$ channel at larger list sizes.

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