In this talk, I will prove a strong converse result on bitwise decoding when communicating with random linear codes over binary symmetric channels (BSC). Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity. This talk is based on joint work with Venkatesan Guruswami and Andrii Riazanov (arXiv:1911.03858), where we proved a more general version of this converse theorem that holds for arbitrary binary-input memoryless symmetric (BMS) channels, and we further used this converse theorem to construct polar codes with near-optimal convergence to channel capacity.
Recorded Talk
Thanks to Min for allowing us to record the talk!