BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20140309T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20131103T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20220815T055319Z
UID:4f8a6658-fec2-4260-a554-aeb24287f586
DTSTART;TZID=America/New_York:20140218T161500
DTEND;TZID=America/New_York:20140218T171500
CREATED:20140212T095224
DESCRIPTION:ABSTRACT:\n\nShannon's monumental 1948 work laid the foundation
s for the rich fields of\ninformation and coding theory. The quest for *
efficient* coding schemes to\napproach Shannon capacity has occupied resea
rchers ever since\, with\nspectacular progress enabling the widespread use
of error-correcting codes\nin practice. Yet the theoretical problem of ap
proaching capacity arbitrarily\nclosely with polynomial complexity remaine
d open except in the special case\nof erasure channels.\n\nIn 2008\, Arika
n proposed an insightful new method for constructing\ncapacity-achieving c
odes based on channel polarization. In this talk\, I will\nbegin by survey
ing Arikan's celebrated construction of polar codes\, and then\ndiscuss ou
r proof (with Patrick Xia) that\, for all binary-input symmetric\nmemoryle
ss channels\, polar codes enable reliable communication at rates\nwithin e
psilon > 0 of the Shannon capacity with block length (delay)\,\nconstructi
on complexity\, and decoding complexity all bounded by a\n*polynomial* in
the gap to capacity\, i.e.\, by poly(1/epsilon). Polar coding\ngives the *
first explicit construction* with rigorous proofs of all these\nproperties
\; previous constructions were not known to achieve capacity with\nless th
an exp(1/epsilon) decoding complexity.\n\nWe establish the capacity-achiev
ing property of polar codes via a direct\nanalysis of the underlying marti
ngale of conditional entropies\, without\nrelying on the martingale conver
gence theorem. This step gives rough\npolarization (noise levels ~ epsilon
for the "good channels")\, which can\nthen be adequately amplified by tra
cking the decay of the channel\nBhattacharyya parameters. Our effective bo
unds imply that polar codes can\nhave block length bounded by poly(1/epsil
on). The generator matrix of such\npolar codes can also be constructed in
deterministic polynomial time by\nalgorithmically computing an adequate ap
proximation of the polarization\nprocess.\n
LAST-MODIFIED:20140212T095224
LOCATION:32-G449
SUMMARY:Polar codes: Reliable communication with complexity scaling polynom
ially in the gap to Shannon capacity
URL:https://calendar.csail.mit.edu/events/124729
END:VEVENT
END:VCALENDAR