Pfister Co-Authors Top Computer Science Theory Paper

Henry Pfister, associate professor of electrical and computer engineering and member of the Information Initiative at Duke, and his coauthors have received a best paper award from the Symposium on the Theory of Computing 2016.

One of the top computer science theory conferences in the world, the symposium names only three papers as award winners each year. The award will be presented during the three-day conference in Cambridge, Mass., on June 18, 2016.

The paper, titled “Reed-Muller Codes Achieve Capacity on Erasure Channels,” introduces a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel. The work shows that, for certain sequences of linear codes, symmetry alone is sufficient to guarantee they achieve capacity.

The other authors of the paper are Shrinivas Kudekar (Qualcomm, Inc.), Santhosh Kumar (Texas A&M University), Marco Mondelli (Swiss Federal Institute of Technology, Lausanne), Eren Şaşoğlu (Intel Corporation), and Rüdiger Urbanke (Swiss Federal Institute of Technology, Lausanne).