Threshold Rates of Codes Ensembles: Linear is Best
share
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 𝔽_q ε-close to capacity to list-recover with error radius ρ and input lists of size ℓ. We show that the list-size L must be at least log_qqℓ-R/ε, 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 log_qqℓ/ε. 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 𝔽_2; and list-of-2 decodability of random linear codes over 𝔽_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 𝔽_2. Further, in both cases we are able to show that the rate is larger than that which is possible for uniformly random codes.
READ FULL TEXT