[CSDM] Venkat Guruswami at theory lunch this friday

[Zeev Dvir]

Hi all,

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.

Location: Room 402, CS building.

-zeev

======================
TITLE:

Polar codes: Reliable communication with complexity polynomial in the gap
to Shannon capacity

ABSTRACT:

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.

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.

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.

Joint work with Patrick Xia.

==============================**========================
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130930/6d0d3b77/attachment.html>