Mahdi Cheraghchi earns NSF CAREER Award to study theoretical roots of error correction and pseudorandomness

Mahdi Cheraghchi, associate professor of computer science at the University of Michigan, has received a National Science Foundation (NSF) CAREER Award to explore the intricate connections between coding theory, particularly list decoding of error-correcting codes, and the theory of pseudorandomness at the core of computer science. The project is titled “Efficiency Considerations in List Decoding and Pseudorandomness Theory.”

Error correction and pseudorandomness are two fundamental aspects of computing, without which none of our modern devices or applications could function. Error correction, a sub-field of coding theory, deals with detecting and fixing the noise and imperfections introduced to data when transmitted or stored on physical media. On the other hand, pseudorandomness enables any number of cryptographic techniques that rely on us being able to reproduce aspects of unpredictability.

Without these fields and their roster of techniques, we would have unreliable, insecure, and likely unrecognizable communication and computing technologies. They also, Cheraghchi argues, both currently suffer from growing gaps between the state of the art in theory and in practice. Error correction, building on work by Claude Shannon that proved both theoretically and practically robust, offers a lot of promising results that go beyond Shannon’s original vision. One such aspect, list decoding, can enable a greater number of errors to be corrected while decoding a message in situations that allow for some ambiguity. However, this is a technique that is rarely seen in action.

“We understand the theory of list decoding very well as far as what I would call ‘applications in theory’ are concerned, but not enough for real-life deployment,” Cheraghchi says.

Likewise, pseudorandomness is well understood in theory, but most practical pseudorandom number generators rely on heuristics that don’t carry fully rigorous guarantees of security. Despite relying on very large and convoluted patterns, they do still create “randomness” that could potentially be recognizable.

In his CAREER research, Cheraghchi will explore the deep theoretical roots that he believes unite these two issues.

“While coding theory is about removing unwanted randomness caused by noise from data, the theory of pseudorandomness is about generating randomness,” Cheraghchi explains. “It can be rigorously proved in many important cases that the task of removing noise from data (as in list decoding) and the task of creating high-quality noise (as in pseudorandomness) are in fact equivalent. Any advancement in the understanding of one will improve our understanding of the other. “

His project studies both aspects hand in hand toward developing theories that are more amenable to practical use.