Algorithms Seminar

Capacity via Symmetry: Why Reed-Muller Codes Achieve Capacity on Erasure Channels

Speaker:Henry Pfister
Date: Thursday, December 7, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke
Lunch will be served.

Abstract

Recently, sequences of error-correcting codes with doubly-transitive permutation groups were shown to achieve capacity on erasure channels under symbol-wise maximum a posteriori (MAP) decoding. From this, it follows that Reed-Muller and primitive narrow-sense BCH codes achieve capacity in the same setting. This talk will present the ideas behind this result in a tutorial fashion. Interestingly, the local correctability of Reed-Muller codes is also a consequence of its permutation group being doubly transitive. An extension to codes whose permutation groups satisfy a condition weaker than double transitivity, such as cyclic codes and product codes, will also be mentioned. The primary tools used in the proof are the sharp-threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer functions.

Biography

Henry D. Pfister received his Ph.D. in electrical engineering in 2003 from the University of California, San Diego and is currently an associate professor in the Electrical and Computer Engineering Department of Duke University with a secondary appointment in Mathematics. Prior to that, he was a professor at Texas A&M University (2006-2014), a post-doctoral fellow at the École Polytechnique Fédérale de Lausanne (2005-2006), and a senior engineer at Qualcomm Corporate R&D in San Diego (2003-2004).

He received the NSF Career Award in 2008 and a Texas A&M ECE Department Outstanding Professor Award in 2010. He is a coauthor of the 2007 IEEE COMSOC best paper in Signal Processing and Coding for Data Storage and a coauthor of a 2016 Symposium on the Theory of Computing (STOC) best paper. He served as an Associate Editor for the IEEE Transactions on Information Theory (2013-2016) and a Distinguished Lecturer of the IEEE Information Theory Society (2015-2016).