We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within \epsilon > 0 of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in 1/\epsilon. Polar coding gives the *first known explicit construction* with rigorous ... more >>>