{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T16:33:22Z","timestamp":1785861202057,"version":"3.56.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T00:00:00Z","timestamp":1552953600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>We develop a systematic approach, based on convex programming and real analysis for obtaining upper bounds on the capacity of the binary deletion channel and, more generally, channels with i.i.d. insertions and deletions. Other than the classical deletion channel, we give special attention to the Poisson-repeat channel introduced by Mitzenmacher and Drinea (IEEE Transactions on Information Theory, 2006). Our framework can be applied to obtain capacity upper bounds for any repetition distribution (the deletion and Poisson-repeat channels corresponding to the special cases of Bernoulli and Poisson distributions). Our techniques essentially reduce the task of proving capacity upper bounds to maximizing a univariate, real-valued, and often concave function over a bounded interval. The corresponding univariate function is carefully designed according to the underlying distribution of repetitions, and the choices vary depending on the desired strength of the upper bounds as well as the desired simplicity of the function (e.g., being only efficiently computable versus having an explicit closed-form expression in terms of elementary, or common special, functions). Among our results, we show the following:<\/jats:p>\n          <jats:p>\n            (1) The capacity of the binary deletion channel with deletion probability\n            <jats:italic>d<\/jats:italic>\n            is at most (1 \u2212\n            <jats:italic>d<\/jats:italic>\n            ) \u03c6 for\n            <jats:italic>d<\/jats:italic>\n            \u2265 1\/2 and, assuming that the capacity function is convex, is at most 1 \u2212\n            <jats:italic>d<\/jats:italic>\n            log(4\/\u03c6) for\n            <jats:italic>d<\/jats:italic>\n            &lt; 1\/2, where \u03c6 = (1 + \u221a5)\/2 is the golden ratio. This is the first nontrivial capacity upper bound for any value of\n            <jats:italic>d<\/jats:italic>\n            outside the limiting case\n            <jats:italic>d<\/jats:italic>\n            \u2192 0 that is fully explicit and proved without computer assistance.\n          <\/jats:p>\n          <jats:p>(2) We derive the first set of capacity upper bounds for the Poisson-repeat channel. Our results uncover further striking connections between this channel and the deletion channel and suggest, somewhat counter-intuitively, that the Poisson-repeat channel is actually analytically simpler than the deletion channel and may be of key importance to a complete understanding of the deletion channel.<\/jats:p>\n          <jats:p>\n            (3) We derive several novel upper bounds on the capacity of the deletion channel. All upper bounds are maximums of efficiently computable, and concave, univariate real functions over a bounded domain. In turn, we upper bound these functions in terms of explicit elementary and standard special functions, whose maximums can be found even more efficiently (and sometimes analytically, for example, for\n            <jats:italic>d<\/jats:italic>\n            = 1\/2).\n          <\/jats:p>","DOI":"10.1145\/3281275","type":"journal-article","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T11:51:18Z","timestamp":1553082678000},"page":"1-79","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Capacity Upper Bounds for Deletion-type Channels"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8957-0306","authenticated-orcid":false,"given":"Mahdi","family":"Cheraghchi","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,3,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19930096"},{"key":"e_1_2_1_2_1","unstructured":"M. Abramowitz and I. A. Stegun. 1974. Handbook of Mathematical Functions With Formulas Graphs and Mathematical Tables. Dover Publications Inc. New York NY.   M. Abramowitz and I. A. Stegun. 1974. Handbook of Mathematical Functions With Formulas Graphs and Mathematical Tables. Dover Publications Inc. New York NY."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2172572"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Belazzougui D."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872397"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2746566"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2621044"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188768"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2018.8437888"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201918)","author":"Cheraghchi M."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 56th Annual Allerton Conference on Communication, Control, and Computing. IEEE","author":"Cheraghchi M."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921889"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2011.6034177"},{"key":"e_1_2_1_14_1","unstructured":"M. H. DeGroot and M. J. Schervish. 2012. Probability and Statistics (4th ed.). Addison-Wesley Boston MA USA.  M. H. DeGroot and M. J. Schervish. 2012. Probability and Statistics (4th ed.). Addison-Wesley Boston MA USA."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing. 573--582","author":"Diggavi S."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864445"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201907)","author":"Diggavi S."},{"key":"e_1_2_1_18_1","first-page":"18","article-title":"Shannon\u2019s theorems for channels with synchronization errors","volume":"3","author":"Dobrushin R. L.","year":"1967","journal-title":"Probl. Peredachi Inf."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/060651380"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.901221"},{"key":"e_1_2_1_21_1","unstructured":"A. Erd\u00e9lyi W. Magnus F. Oberhettinger and F. G. Tricomi. 1953. Higher Transcendental Functions. Vol. 1. McGraw--Hill New York NY.  A. Erd\u00e9lyi W. Magnus F. Oberhettinger and F. G. Tricomi. 1953. Higher Transcendental Functions. Vol. 1. McGraw--Hill New York NY."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046210"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2010.110310.090039"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.75.1.40"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Guruswami V."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090252"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2659765"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201910)","author":"Kalai A."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2262020"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40315-015-0128-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1129104"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.817449"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.2008121"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAB.24.000739"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-PS141"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881844"},{"key":"e_1_2_1_37_1","first-page":"21","article-title":"More accurate approximations for the gamma function","volume":"9","author":"Nemes G.","year":"2011","journal-title":"Thai J. Math."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.4079"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2368553"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796406"},{"key":"e_1_2_1_41_1","first-page":"6","article-title":"Capacity of a pulse amplitude modulated direct detection photon channel. IEE Proce","volume":"137","author":"Shamai S.","year":"1990","journal-title":"I Commun. Speech Vis."},{"key":"e_1_2_1_42_1","first-page":"17","article-title":"Sequential decoding for a binary channel with dropouts and insertions","volume":"5","author":"Zigangirov K. S.","year":"1969","journal-title":"Probl. Inf. Transm."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3281275","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3281275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:17Z","timestamp":1750208237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3281275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,19]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3281275"],"URL":"https:\/\/doi.org\/10.1145\/3281275","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,19]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}