By Peter Murphy

The 2006 paper that solved this problem by achieving what researchers call “list decoding capacity” — the theoretical limit for recovering heavily corrupted data — received the 2026 Association for Computing Machinery’s Symposium on Theory of Computing (STOC) Test of Time Award.

“Let’s say you want to communicate, and this could be calling someone on your cell phone, or it could be communication over time, which means you’re storing something in memory,” said Atri Rudra, the paper’s co-author and inaugural chair and professor in the University at Buffalo Department of AI and Society. “When you’re speaking on the phone, your voice gets converted and the signals go through air. There can be data loss, and the signal isn’t received as it should be. Similarly, when you store something in memory, that memory location can get corrupted.”

The problem was open, according to Rudra, for close to 50 years after electrical engineers and computer scientists Claude Shannon and Richard Hamming first investigated it as part of their foundational works on communication theory. Adding redundancy, they found, is one way to address errors that could occur when transporting or storing data.

“Instead of sending ‘b a d,’ you can send ‘b b b a a a d d d,’ right?” Rudra said. “So, if you lose any of the d’s, or if one of them flips, you can still make the message out. If you’re expecting one error, repeating everything three times works, but if you’re expecting 10 errors, you don’t want to repeat things 21 times, right? Shannon and Hamming started this whole area of what’s called error correcting codes or coding theory and asked what the best possible way is to protect against errors.”

Shannon and Hamming wrote their defining papers on the subject in the late 1940s. They figured out the mathematical limits, and the new problem facing error correcting codes was whether researchers could build a coding system that reaches the mathematical limits and can be decoded efficiently from adversarial errors. Rudra and his advisor at the time, Venkatesan Guruswami, solved this problem with their 2006 paper “Explicit capacity-achieving list-decodable codes.”

Their key breakthrough was the folded Reed-Solomon coding method that Rudra and Guruswami developed. The Reed-Solomon coding method treated pieces of data individually and added polynomial and redundant check symbols to mathematically guarantee recovery of missing data. Rudra and Guruswami grouped pieces of data together, or folding, which made patterns in errors easier to recognize and correct.

“This was originally an electrical engineering concept that moved into computer science through computational complexity and the study of limits of computation. In computer science in particular, people began looking at these in proof verification,” Rudra said. “Can you design proofs of statements that you can verify by just spot checking it in five places?”

The spot-checking method Rudra described was roughly how researchers advanced this concept.

“The regime where this error and redundancy matters is when you are correcting close to 100%, or close to the entire redundancy. For any reasonable set of data, that is a very harsh requirement and doesn’t really happen in practice. Typically, you would not be expecting more than 10% corruption,” Rudra said.

Twenty years after publication, the paper remains influential “for the discovery of the first family of codes achieving list-decoding capacity, thereby introducing foundational techniques and useful black-box results that have had lasting impact on coding theory and theoretical computer science,” according to STOC.

The paper holds personal significance for Rudra as well.

“This work was my first result that got a lot of attention. This was the first big thing I was able to do as a researcher,” Rudra said. “In that sense, it’s very near and dear to my heart.”