Error-Correcting Codes & Algorithms

Sunny Chung | February 14, 2011

International Congress of Mathematicians Award Ceremony, Daniel Spielman (third from right). Image courtesy of Sulekha News Hopper.

Recently, the International Mathematical Union (IMU) awarded Daniel Spielman, Yale Professor of Applied Mathematics and Computer Science, the legendary honor of the Rolf Nevanlinna Prize.

As a child, Spielman had always been fascinated by computers. He recalls, “I was in the fourth grade when I first learned about computers. After that, I kept on begging my parents to get me one until I had finally received one in the seventh grade.” This curiosity and passion for computers continued to grow over the years.

Among many of Spielman’s groundbreaking contributions, the IMU recognized three in particular: the design of error-correcting code, smoothed analysis of algorithms, and advancements in the solution of systems of linear equations.

Error-correcting code techniques that Spielman and his team developed are necessary to ensure that present-day communication, such as internet packet-loss and preservation of security, is maintained at an optimal level. Essentially, data that is transmitted through channels are often subjected to noise, which may obscure information necessary for data processing. For example, files and data transmitted through the Internet by email and uploading are often subjected to extra information, including IP addresses and recipient information, which may obscure the important information. Spielman and his team developed an error-correcting code that tries to erase these redundant and unnecessary data using probabilistic models, thereby establishing efficient models that serve to accurately render the data in good faith.

Furthermore, Spielman has worked on smoothed analysis of algorithms in linear equations to develop a very influential theorem for the Simplex Method. As one of the top ten most influential algorithms in the twentieth century, the Simplex Method is a very efficient technique used to solve linear systems. However, mathematicians and computer scientists have been perplexed by why it works and how long it takes for the computer to actually execute the code. Spielman and his team, in light of this problem, developed and proved a theorem that rigorously shows that the algorithm can usually be solved in quasi-linear time. In essence, the amount of time required to solve a linear system using the Simplex is only linearly related to the amount of variables that needs to be solved. This important discovery allows mathematicians and computer scientists to safely rely on the algorithm without worrying about the excess time needed to solve linear systems, thereby eliminating inefficiencies that are frequently found in applications of other various fields, ranging from meteorology to economics.

Spielman acknowledges that his journey towards the prize has not always been so smooth. He cautions, “Usually discouragement was standard for theoretical work. I would sometimes go weeks writing down code and still nothing seemed to work.” The only thing that kept him motivated was when those rare ideas suddenly did work. He states, “It was because of that adrenaline rush that let me go on for a very long time – because there’s always going to be discouragement. That’s the norm when you’re dealing with theoretical research.”

Even after receiving the Nevanlinna Prize, which was one of his greatest life goals, he still continues to research tough questions and ideas in both mathematics and computer science. Emphasizing that drive is key to one’s academic career, Spielman shares, “You should always work on hard problems and never give up. Be prepared to think about problems for years until you understand it inside and out. Always be excited in what you’re thinking.” In the end, it was that same drive that allowed Spielman to achieve one of the greatest honors in mathematics.