BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/798
DTSTAMP:20230914T125938Z
SUMMARY:General Strong-Polarization
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Paulson School of\nEngine
 ering and Applied Sciences\n339 Maxwell Dworkin\n33 Oxford Street\nCambrid
 ge\, MA 02138\nUnited States of America)\n\nAbstract: \nA martingale is a 
 sequence of random variables that maintain their future expected value con
 ditioned on the past.  A $[0\,1]$-bounded martingale is said to polarize 
 if it converges in the limit to either $0$ or $1$ with probability $1$.  
 A martingale is said to polarize strongly\, if in $t$ steps it is sub-expo
 nentially close to its limit with all but exponentially small probability.
  In 2008\, Arikan built a powerful class of error-correcting codes called 
 Polar codes. The essence of his theory associates a martingale with every 
 invertible square matrix over a field (and a channel) and showed that pola
 rization of the martingale leads to a construction of codes that converge 
 to Shannon capacity. In 2013\, Guruswami and Xia\,  and independently Has
 sani et al. showed that strong polarization of the Arikan martingale leads
  to codes that converge to Shannon capacity at finite block lengths\, spec
 ifically at lengths that are inverse polynomial in the gap to capacity\, t
 hereby resolving a major mathematical challenge associated with the attain
 ment of Shannon capacity.\n\nWe show that a simple necessary condition for
  an invertible matrix to polarize over any non-trivial channel is also suf
 ficient for strong polarization over all symmetric channels over all prime
  fields. Previously the only matrix which was known to polarize strongly w
 as the $2\\times 2$ Hadamard matrix. In addition to the generality of our 
 result\, it also leads to arguably simpler proofs. The essence of our proo
 f is a ``local definition'' of polarization which only restricts the evolu
 tion of the martingale in a single step\, and a general theorem showing th
 e local polarization suffices for strong polarization.\n\nIn this talk I w
 ill introduce polarization and polar codes and\, time permitting\, present
  a full proof of our main theorem. No prior background on polar codes will
  be assumed (based on joint work with Jaroslaw Blasiok\, Venkatesan Gurusw
 ami\, Preetum Nakkiran and Atri Rudra).\n
URL:https://www.tcs.tifr.res.in/web/events/798
DTSTART;TZID=Asia/Kolkata:20170809T143000
DTEND;TZID=Asia/Kolkata:20170809T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR