<div dir="ltr">Hi all,<div><br></div><div>Venkat Guruswami (CMU) will speak this friday, Oct 4 at theory lunch. See title/abstract below. Lunch will be served at 11:45 and the talk will start at noon. </div><div><br></div>
<div>Location: Room 402, CS building.</div><div><br></div><div>-zeev</div><div><br></div><div><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">======================</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<span style="font-family:arial,sans-serif;font-size:12.800000190734863px">TITLE:</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<span style="font-family:arial,sans-serif;font-size:12.800000190734863px">Polar codes: Reliable communication with complexity polynomial in the gap to Shannon capacity</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">ABSTRACT:</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">We prove that, for all binary-input symmetric memoryless channels, Arikan's celebrated polar codes enable reliable communication at rates within epsilon > 0 of the Shannon capacity with block length (delay), construction complexity, and decoding complexity all bounded by a *polynomial* in the gap to capacity, i.e., by poly(1/epsilon). Polar coding gives the *first known explicit construction* with rigorous proofs of all these properties.</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">We establish the capacity-achieving property of polar codes via a direct analysis of the underlying martingale of conditional entropies, without relying on the martingale convergence theorem. This step gives rough polarization (noise levels ~ epsilon for the "good channels"), which can then be adequately amplified by tracking the decay of the channel Bhattacharyya parameters.</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">Our effective bounds imply that polar codes can have block length (and consequently also encoding/decoding complexity) that is bounded by poly(1/epsilon). We also show that the generator matrix of such polar codes can be constructed in polynomial time by algorithmically computing an adequate approximation of the polarization process.</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><span style="font-family:arial,sans-serif;font-size:12.800000190734863px">Joint work with Patrick Xia.</span><br style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<br style="font-family:arial,sans-serif;font-size:12.800000190734863px"><div style="font-family:arial,sans-serif;font-size:12.800000190734863px">==============================<u></u>========================</div></div></div>