{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:40:08Z","timestamp":1750185608260,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ONR","award":["N00014-15-1-2388"],"award-info":[{"award-number":["N00014-15-1-2388"]}]},{"name":"NSF","award":["CCF-1422045, CCF-1563742, CCF-1814603, CCF 1565641, CCF 1715187, DGE1144152 and CCF-1717134"],"award-info":[{"award-number":["CCF-1422045, CCF-1563742, CCF-1814603, CCF 1565641, CCF 1715187, DGE1144152 and CCF-1717134"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            Ar\u0131kan\u2019s exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix\n            <jats:italic>M<\/jats:italic>\n            , a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the\n            <jats:italic>polarization<\/jats:italic>\n            of an associated [0, 1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Ar\u0131kan showed appropriate polarization of the martingale associated with the matrix (\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            = ( 1 1 0 1) to get capacity achieving codes. His analysis was later extended to all matrices\n            <jats:italic>M<\/jats:italic>\n            that satisfy an obvious necessary condition for polarization.\n          <\/jats:p>\n          <jats:p>\n            While Ar\u0131kan\u2019s theorem does not guarantee that the codes achieve capacity at small blocklengths (specifically in length, which is a polynomial in ( 1\u03b5 ) where (\u03b5) is the difference between the capacity of a channel and the rate of the code), it turns out that a \u201cstrong\u201d analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with (\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ) such a strong polarization was shown in two independent works (Guruswami and Xia (IEEE IT\u201915) and Hassani et\u00a0al. (IEEE IT\u201914)), thereby resolving a major theoretical challenge associated with the efficient attainment of Shannon capacity.\n          <\/jats:p>\n          <jats:p>\n            In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more general, our proofs of strong polarization are (in our view) also much simpler and modular. Key to our proof is a notion of\n            <jats:italic>local polarization<\/jats:italic>\n            that only depends on the evolution of the martingale in a single time step. We show that local polarization always implies strong polarization. We then apply relatively simple reasoning about conditional entropies to prove local polarization in very general settings. Specifically, our result shows strong polarization over all prime fields and leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels. We show how to use our analyses to achieve exponentially small error probabilities at lengths inverse polynomial in the gap to capacity. Indeed we show that we can essentially match any error probability while maintaining lengths that are only inverse polynomial in the gap to capacity.\n          <\/jats:p>","DOI":"10.1145\/3491390","type":"journal-article","created":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T19:33:42Z","timestamp":1646336022000},"page":"1-67","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["General Strong Polarization"],"prefix":"10.1145","volume":"69","author":[{"given":"Jaros\u0142aw","family":"B\u0142asiok","sequence":"first","affiliation":[{"name":"Department of Computer Science, Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7926-3396","authenticated-orcid":false,"given":"Preetum","family":"Nakkiran","sequence":"additional","affiliation":[{"name":"Halicio\u011flu Data Science Institute, University of California San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Department, University at Buffalo, Buffalo, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,3]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2201374"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2021379"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1701116.1701126"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188816"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.34"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/047174882X"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1561\/0100000041"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2268946"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108591034"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3038806"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2013.6620402"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2359197"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384323"},{"key":"e_1_3_3_15_2","volume-title":"Essential Coding Theory","author":"Guruswami Venkatesan","year":"2019","unstructured":"Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. March 15, 2019. Essential Coding Theory. Retrieved June 13, 2021 from https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book\/index.html."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833229"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2371819"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2341919"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"e_1_3_3_20_2","first-page":"1","volume-title":"Proceedings of the IEEE Information Theory Workshop","author":"Korada Satish Babu","year":"2010","unstructured":"Satish Babu Korada. 2010. Polar codes for Slepian-Wolf, Wyner-Ziv, and Gelfand-Pinsker. In Proceedings of the IEEE Information Theory Workshop. 1\u20135."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2080990"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2010.5513579"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2162275"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2616117"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2312181"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2915595"},{"key":"e_1_3_3_27_2","volume-title":"Information and Information Stability of Random Variables and Processes","author":"Pinsker M. S.","year":"1964","unstructured":"M. S. Pinsker. 1964. Information and Information Stability of Random Variables and Processes. Holden-Day."},{"key":"e_1_3_3_28_2","first-page":"689","volume-title":"Transactions of the 3rd Prague Conference on Information Theory","author":"Strassen Volker","year":"1962","unstructured":"Volker Strassen. 1962. Asymptotische abschatzungen in shannon\u2019s informationstheories. In Transactions of the 3rd Prague Conference on Information Theory. 689\u2013723."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2272694"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2410251"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3041570"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6874845"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255380682"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491390","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491390","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:21Z","timestamp":1750183761000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491390"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,3]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3491390"],"URL":"https:\/\/doi.org\/10.1145\/3491390","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2022,3,3]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}