A Caltech Library Service

The Birthday Problem and Zero-Error List Codes

Noorzad, Parham and Effros, Michelle and Langberg, Michael and Kostina, Victoria (2021) The Birthday Problem and Zero-Error List Codes. IEEE Transactions on Information Theory, 67 (9). pp. 5791-5803. ISSN 0018-9448. doi:10.1109/tit.2021.3100806.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A key result of classical information theory states that if the rate of a randomly generated codebook is less than the mutual information between the channel’s input and output, then the probability that that codebook has negligible error goes to one as the blocklength goes to infinity. In an attempt to bridge the gap between the probabilistic world of classical information theory and the combinatorial world of zero-error information theory, this work derives necessary and sufficient conditions on the rate so that the probability that a randomly generated codebook operated under list decoding (for any fixed list size) has zero error probability goes to one as the blocklength goes to infinity. Furthermore, this work extends the classical birthday problem to an information-theoretic setting, which results in the definition of a “noisy” counterpart of Rényi entropy, analogous to how mutual information can be considered a noisy counterpart of Shannon entropy.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper
Noorzad, Parham0000-0002-0201-3791
Effros, Michelle0000-0003-3757-0675
Langberg, Michael0000-0002-7470-0718
Kostina, Victoria0000-0002-2406-7440
Additional Information:© 2021 IEEE. Manuscript received March 3, 2020; revised April 3, 2021; accepted July 15, 2021. Date of publication July 28, 2021; date of current version August 25, 2021. This work was supported by the National Science Foundation under Grant 1321129, Grant 1527524, and Grant 1526771. This article was presented in part at the 2017 IEEE International Symposium of Information Theory.
Funding AgencyGrant Number
Subject Keywords:Birthday problem, collision probability, hash function, hypergraph, Körner graph entropy, list decoding, Motzkin-Straus theorem, random coding, Rényi entropy, zero-error channel capacity
Issue or Number:9
Record Number:CaltechAUTHORS:20210825-143502652
Persistent URL:
Official Citation:P. Noorzad, M. Effros, M. Langberg and V. Kostina, "The Birthday Problem and Zero-Error List Codes," in IEEE Transactions on Information Theory, vol. 67, no. 9, pp. 5791-5803, Sept. 2021, doi: 10.1109/TIT.2021.310080
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110412
Deposited By: Tony Diaz
Deposited On:25 Aug 2021 17:29
Last Modified:01 Sep 2021 17:28

Repository Staff Only: item control page