تقرير
Threshold Rates of Codes Ensembles: Linear is Best
| العنوان: | Threshold Rates of Codes Ensembles: Linear is Best |
|---|---|
| المؤلفون: | Resch, Nicolas, Yuan, Chen |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Information Theory |
| الوصف: | In this work, we prove new results concerning the combinatorial properties of random linear codes. Firstly, we prove a lower bound on the list-size required for random linear codes over $\mathbb F_q$ $\varepsilon$-close to capacity to list-recover with error radius $\rho$ and input lists of size $\ell$. We show that the list-size $L$ must be at least $\frac{\log_q\binom{q}{\ell}-R}{\varepsilon}$, where $R$ is the rate of the random linear code. As a comparison, we also pin down the list size of random codes which is $\frac{\log_q\binom{q}{\ell}}{\varepsilon}$. This leaves open the possibility (that we consider likely) that random linear codes perform better than random codes for list-recoverability, which is in contrast to a recent gap shown for the case of list-recovery from erasures (Guruswami et al., IEEE TIT 2021B). Next, we consider list-decoding with constant list-sizes. Specifically, we obtain new lower bounds on the rate required for list-of-$3$ decodability of random linear codes over $\mathbb F_2$; and list-of-$2$ decodability of random linear codes over $\mathbb F_q$ (for any $q$). This expands upon Guruswami et al. (IEEE TIT 2021A) which only studied list-of-$2$ decodability of random linear codes over $\mathbb F_2$. Further, in both cases we are able to show that the rate is larger than that which is possible for uniformly random codes. Comment: 37 pages, 2 figures. Accepted to ICALP 2022 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2205.01513 |
| رقم الأكسشن: | edsarx.2205.01513 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |