We prove that, at least for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but 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 construction, encoding and decoding. Specifically, for any fixed $\delta > 0$, we exhibit binary linear codes that ensure reliable communication at rates within $\varepsilon > 0$ of capacity with block length $n=O(1/\varepsilon^{2+\delta})$, construction complexity $\Theta(n)$, and encoding/decoding complexity $\Theta(n\log n)$. Our proof is based on the construction and analysis of binary polar codes with large kernels. It was recently shown that, for all binary-input symmetric memoryless channels, conventional polar codes (based on a $2\times 2$ kernel) allow reliable communication at rates within $\varepsilon 查看全文>>