CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20170816-163747105

[img] PDF - Submitted Version
See Usage Policy.

223Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170816-163747105

Abstract

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
https://doi.org/10.1109/ISIT.2017.8006809DOIArticle
http://ieeexplore.ieee.org/document/8006809/PublisherArticle
https://arxiv.org/abs/1802.04719arXivDiscussion Paper
ORCID:
AuthorORCID
Noorzad, Parham0000-0002-0201-3791
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1321129
NSFCCF-1527524
NSFCCF-1526771
Record Number:CaltechAUTHORS:20170816-163747105
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170816-163747105
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
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:16 Aug 2017 23:54
Last Modified:02 Apr 2019 21:54

Repository Staff Only: item control page