{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T04:39:25Z","timestamp":1787027965764,"version":"build-2736575974"},"reference-count":19,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T00:00:00Z","timestamp":1745712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2127605"],"award-info":[{"award-number":["2127605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The notion of \u03b4-mutual information between non-stochastic uncertain variables is introduced as a generalization of Nair\u2019s non-stochastic information functional. Several properties of this new quantity are illustrated and used in a communication setting to show that the largest \u03b4-mutual information between received and transmitted codewords over \u03f5-noise channels equals the (\u03f5,\u03b4)-capacity. This notion of capacity generalizes the Kolmogorov \u03f5-capacity to packing sets of overlap at most \u03b4 and is a variation of a previous definition proposed by one of the authors. Results are then extended to more general noise models, including non-stochastic, memoryless, and stationary channels. The presented theory admits the possibility of decoding errors, as in classical information theory, while retaining the worst-case, non-stochastic character of Kolmogorov\u2019s approach.<\/jats:p>","DOI":"10.3390\/e27050472","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T09:00:39Z","timestamp":1745917239000},"page":"472","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Kolmogorov Capacity with Overlap"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8462-7892","authenticated-orcid":false,"given":"Anshuka","family":"Rangi","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of California at San Diego, 9500 Gilman Drive, Mail Code 0407, La Jolla, CA 92093-0407, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4057-8152","authenticated-orcid":false,"given":"Massimo","family":"Franceschetti","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of California at San Diego, 9500 Gilman Drive, Mail Code 0407, La Jolla, CA 92093-0407, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,4,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/TAC.2013.2241491","article-title":"A nonstochastic information theory for communication and state estimation","volume":"58","author":"Nair","year":"2013","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1090\/S0002-9939-1967-0207590-3","article-title":"On a problem of C.E. Shannon in graph theory","volume":"18","author":"Rosenfeld","year":"1967","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","article-title":"The zero error capacity of a noisy channel","volume":"2","author":"Shannon","year":"1956","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Nair, G.N. (2012, January 10\u201313). A nonstochastic information theory for feedback. Proceedings of the 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Maui, HI, USA.","DOI":"10.1109\/CDC.2012.6425874"},{"key":"ref_6","first-page":"3","article-title":"\u03f5-entropy and \u03f5-capacity of sets in functional spaces","volume":"14","author":"Tikhomirov","year":"1959","journal-title":"Uspekhi Mat. Nauk"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1109\/TIT.2016.2647602","article-title":"Information without rolling dice","volume":"63","author":"Lim","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"5903","DOI":"10.1109\/TIT.2021.3100931","article-title":"A Signal-Space Distance Measure for Nondispersive Optical Fiber","volume":"67","author":"Borujeny","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","unstructured":"Ferng, C.S., and Lin, H.T. (2011, January 13\u201315). Multi-label classification with error-correcting codes. Proceedings of the Asian Conference on Machine Learning, Taoyuan, Taiwan."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.ifacol.2018.12.046","article-title":"Estimation and Control over a Nonstochastic Binary Erasure Channel","volume":"51","author":"Saberi","year":"2018","journal-title":"IFAC-PapersOnLine"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Saberi, A., Farokhi, F., and Nair, G.N. (2019, January 7\u201312). State Estimation via Worst-Case Erasure and Symmetric Channels with Memory. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849743"},{"key":"ref_12","unstructured":"Verma, G., and Swami, A. (2019, January 8\u201314). Error correcting output codes improve probability estimation and adversarial robustness of deep neural networks. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_13","unstructured":"Weng, T.W., Zhang, H., Chen, P.Y., Yi, J., Su, D., Gao, Y., Hsieh, C.J., and Daniel, L. (2018). Evaluating the robustness of neural networks: An extreme value theory approach. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Wiese, M., Johansson, K.H., Oechtering, T.J., Papadimitratos, P., Sandberg, H., and Skoglund, M. (2016, January 10\u201315). Uncertain wiretap channels and secure estimation. Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541650"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.2307\/1427934","article-title":"Sample mean based index policies with O (log n) regret for the multi-armed bandit problem","volume":"27","author":"Agrawal","year":"1995","journal-title":"Adv. Appl. Probab."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539701398375","article-title":"The nonstochastic multiarmed bandit problem","volume":"32","author":"Auer","year":"2002","journal-title":"SIAM J. Comput."},{"key":"ref_17","unstructured":"Rangi, A., and Franceschetti, M. (2019, January 16\u201318). Online learning with feedback graphs and switching costs. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Naha, Japan."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Rangi, A., and Franceschetti, M. (2019, January 7\u201312). Towards a non-stochastic information theory. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849728"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Rangi, A., and Franceschetti, M. (2021, January 12\u201320). Channel Coding Theorems in Non-stochastic Information Theory. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518008"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/5\/472\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:22:34Z","timestamp":1760030554000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/5\/472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,27]]},"references-count":19,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2025,5]]}},"alternative-id":["e27050472"],"URL":"https:\/\/doi.org\/10.3390\/e27050472","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,27]]}}}