A Caltech Library Service

The birthday problem and zero-error list codes

Noorzad, Parham and Effros, Michelle and Langberg, Michael and Kostina, Victoria (2017) The birthday problem and zero-error list codes. In: 2017 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 1648-1652. ISBN 978-1-5090-4096-4.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


As an attempt to bridge the gap between classical information theory and the combinatorial world of zero-error information theory, this paper studies the performance of randomly generated codebooks over discrete memoryless channels under a zero-error constraint. This study allows the application of tools from one area to the other. Furthermore, it leads to an information-theoretic formulation of the birthday problem, which is concerned with the probability that in a given population, a fixed number of people have the same birthday. Due to the lack of a closed-form expression for this probability when the distribution of birthdays is not uniform, the resulting computation is not feasible in some applications; the information-theoretic formulation, however, can be analyzed for all distributions.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Noorzad, Parham0000-0002-0201-3791
Langberg, Michael0000-0002-7470-0718
Kostina, Victoria0000-0002-2406-7440
Additional Information:© 2017 IEEE. This material is based upon work supported by the National Science Foundation under Grant Numbers 1321129, 1527524, and 1526771. The first author thanks Ming Fai Wong for helpful discussions regarding an earlier version of Theorem 2.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20170816-163747105
Persistent URL:
Official Citation:P. Noorzad, M. Effros, M. Langberg and V. Kostina, "The birthday problem and zero-error list codes," 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017, pp. 1648-1652. doi: 10.1109/ISIT.2017.8006809
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80532
Deposited By: Kristin Buxton
Deposited On:16 Aug 2017 23:54
Last Modified:14 Feb 2020 21:08

Repository Staff Only: item control page