Lower Bounds on List Decoding Capacity using Error Exponents

Zhang, Yihan and Vatedka, Shashank (2022) Lower Bounds on List Decoding Capacity using Error Exponents. In: 2022 IEEE International Symposium on Information Theory, ISIT 2022, 26 June 2022 through 1 July 2022, Espoo.

[img] Text
IEEE_Information_Theory_Proceedings.pdf - Published Version
Restricted to Registered users only

Download (1MB) | Request a copy


We study the problem of characterizing the maximal rates of list decoding in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and real N > 0, we say that a subset C ⊂ Rn is an (N,L - 1)-multiple packing or an (N,L- 1)-list decodable code if every Euclidean ball of radius √ nN in ℝn contains no more than L - 1 points of C. We study this problem with and without ℓ2 norm constraints on C, and derive the best-known lower bounds on the maximal rate for (N,L-1) multiple packing. Our bounds are obtained via error exponents for list decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious inequality which relates the error exponent, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We derive various bounds on the error exponent for list decoding in both bounded and unbounded settings which could be of independent interest beyond multiple packing. © 2022 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Vatedka, Shashankhttps://orcid.org/0000-0003-2384-9392
Item Type: Conference or Workshop Item (Paper)
Additional Information: YZ has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]. The work of SV was supported by a seed grant from IIT Hyderabad and SRG/2020/000910 by SERB (DST), India.
Uncontrolled Keywords: Error exponent; Euclidean; Euclidean spaces; List decoding capacities; List-decodable codes; List-decoding; Low bound; Maximal rates; Multiple packings; Positive integers
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 02 Sep 2022 04:56
Last Modified: 02 Sep 2022 04:56
URI: http://raiith.iith.ac.in/id/eprint/10387
Publisher URL: http://doi.org/10.1109/ISIT50566.2022.9834815
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10387 Statistics for this ePrint Item