Analyzing Algorithms: Computer Scientist Daniel Spielman Wins MacArthur Genius Grant

Julia Rothchild
By Julia Rothchild February 19, 2013 15:48

Daniel Spielman is the Henry Ford II Professor of Computer Science, Mathematics, and Applied Science. Courtesy of the John D. & Catherine T. MacArthur Foundation.

Daniel Spielman ’92, Henry Ford II Professor of Computer Science, Mathematics, and Applied Science, was named one of this year’s MacArthur Fellows in October. The MacArthur Foundation, which aims to financially support people who show exceptional merit in their respective fields, awarded $500,000 to Spielman, to be given out evenly over the next five years.

Spielman is a theoretical computer scientist. His work focuses on designing algorithms that optimize the speed of data transmission. He says in an interview for the MacArthur Foundation that he enjoys his work on algorithms because “you get to use just pure reasoning, just thinking about mathematics to come up with actually better ways of doing things.”

Spielman’s work focuses on algorithms as they relate to coding theory. Courtesy of the John D. & Catherine T. MacArthur Foundation.

Within the mathematical study of codes, called coding theory, he develops algorithms that quickly recover errors in the transmission of information over noisy channels. This research is applicable to many areas, including cell phone communication speed: “the limiting factor in the speed at which your cell phone can communicate is the amount of interference that it has when it communicates,” Spielman explains. “The way you deal with that is through error-correcting codes.”

Spielman’s other research interests include improving ways of analyzing algorithm efficiency. He found that the traditional method of analyzing efficiency — measuring how an algorithm performs in worst-case scenarios — yields results that differ from those attained in practical applications of that algorithm. Spielman developed the theory of smoothed analysis, which asserts that adding elements of randomness to an algorithm’s input produces a much more accurate conclusion about the algorithm’s efficiency. This theory, like his other discoveries in the field of efficient algorithms, is influential throughout a variety of fields. It is for these contributions that Professor Spielman won the MacArthur Genius Grant this year.

Spielman has won numerous other prestigious prizes, including the Gödel Prize, the Nevanlinna Prize, and the Simons Investigator Award. Courtesy of the John D. & Catherine T. MacArthur Foundation.

Julia Rothchild
By Julia Rothchild February 19, 2013 15:48