Capacity via Symmetry: Extensions and Practical Consequences

Tuesday, April 4, 2017 - 4:00pm to Wednesday, April 5, 2017 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Henry Pfister


Duke University

Building and Room Number



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. We extend this result to a larger class of codes by considering codes whose permutation groups satisfy a condition weaker than double transitivity. In particular, the larger class contains many cyclic codes and product codes. For example, we find that iterated products of single-parity check codes achieve capacity under MAP decoding. The benefits of symmetry are also considered for low-complexity decoding. In particular, the existence of a single low-weight parity check implies the existence of many low-weight parity checks. This fact can be leveraged by various low-complexity decoding techniques to achieve surprisingly good performance.


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). His current research interests include information theory, communications, probabilistic graphical models, and machine learning.