@inproceedings{2279008dea444c2c94a13b0610777ec6,
title = "Fundamental Limits of Database Alignment",
abstract = "We consider the problem of aligning a pair of databases with correlated entries. We introduce a new measure of correlation in a joint distribution that we call cycle mutual information. This measure has operational significance: it determines whether exact recovery of the correspondence between database entries is possible for any algorithm. Additionally, there is an efficient algorithm for database alignment that achieves this information theoretic threshold.",
author = "Daniel Cullina and Prateek Mittal and Negar Kiyavash",
note = "Funding Information: This work was supported in part by NSF grants CCF 16-19216, CCF 16-17286, and CNS 15-53437. Funding Information: ACKNOWLEDGEMENT This work was supported in part by NSF grants CCF 16-19216, CCF 16-17286, and CNS 15-53437.; 2018 IEEE International Symposium on Information Theory, ISIT 2018 ; Conference date: 17-06-2018 Through 22-06-2018",
year = "2018",
month = aug,
day = "15",
doi = "10.1109/ISIT.2018.8437908",
language = "English (US)",
isbn = "9781538647806",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "651--655",
booktitle = "2018 IEEE International Symposium on Information Theory, ISIT 2018",
address = "United States",
}