--- res: bibo_abstract: - We prove that, at least for the binary erasure channel, the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but, in fact, do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure reliable communication at rates within ε > 0 of capacity with block length n = O(1/ε 2+δ ), construction complexity Θ(n), and encoding/decoding complexity Θ(n log n).@eng bibo_authorlist: - foaf_Person: foaf_givenName: Arman foaf_name: Fazeli, Arman foaf_surname: Fazeli - foaf_Person: foaf_givenName: Hamed foaf_name: Hassani, Hamed foaf_surname: Hassani - foaf_Person: foaf_givenName: Marco foaf_name: Mondelli, Marco foaf_surname: Mondelli foaf_workInfoHomepage: http://www.librecat.org/personId=27EB676C-8706-11E9-9510-7717E6697425 orcid: 0000-0002-3242-7020 - foaf_Person: foaf_givenName: Alexander foaf_name: Vardy, Alexander foaf_surname: Vardy bibo_doi: 10.1109/itw.2018.8613428 dct_date: 2018^xs_gYear dct_language: eng dct_publisher: IEEE@ dct_title: 'Binary linear codes with optimal scaling: Polar codes with large kernels@' ...