Improved lower bounds on the sizes of error-correcting codes for list decoding

摘要

Elias (1991) derived upper and lower bounds on the sizes of error-correcting codes for list decoding. The asymptotic values of his lower bounds for linear codes and for nonlinear codes are separated. The present authors derive improved lower bounds for linear and for nonlinear codes. They conjecture their two bounds are identical. However, they were able to verify this only for small lists.