Speaker: Daniel Alan Spielman

Title: The Complexity of Communication Near Channel Capacity

When/Where: Monday, January 27 4:00 PM, 400 AKW

Abstract: In his seminal 1948 paper, Shannon defined the capacity of a communication channel, proved that one could use error-correcting codes to
reliably transmit information over a channel at any rate less than its capacity, and proved that one could not reasonably communicate at any rate above its capacity. However, the error correcting codes proved to exist by Shannon could not be encoded or decoded efficiently. Thus, the construction of computationally efficient error-correcting codes became one of the principal goals of the new field of information theory. In the last few
years, we have made significant progress towards these goals: low-density parity check and turbo-like codes have provided computationally cheap communication at rates within small fractions of the capacity of many classically studied communication channels. As opposed to the algebraic techniques popular in the previous two decades, these codes are designed, analyzed, and implemented using analytical and probabilistic techniques.
In this talk, we will explain how these codes work, how they are designed, and how they may be further improved. We will take care to distinguish between what we can prove, what we can heuristically reason, and what we know from experiment. Some of the work to be presented is joint with M. Luby, M. Mitzenmacher, and M. A. Shokrollahi.

Daniel Alan Spielman received the B.A. degrees in Mathematics and Computer Science from Yale in 1992 and the Ph.D. degree in Applied Mathematics from the Massachusetts Institute of Technology in 1995. He spent 1995-1996 in the Computer Science department at the University of California at Berkeley, where he was supported by an NSF Mathematical Sciences Postdoctoral Fellowship. Since 1996, he has been in the department of Applied Mathematics at the Massachusetts Institute of Technology, where he is now an Associate Professor. Dr. Spielman is a recipient of the Association for Computing Machinery's Doctoral Dissertation Award, an NSF CAREER award, an Alfred P. Sloan Foundation Research Fellowship, and the 2002 Information Theory Society Paper Award.