What is coded computing and why is it vital for cellphones and the internet?

Coded computing fascinates Qian Yu, a PhD student in the Ming Hsieh Department of Electrical Engineering. It’s a new field developed at the USC Viterbi School of Engineering in the lab of Salman Avestimehr, Yu’s adviser.

Yu’s extensive research resulted in a 2018 Google Fellowship in machine learning.

Coded computing and the internet

So what is coded computing and why is it important? To understand Yu’s work and its impact, we have to go back in time to the early days of the internet and cellphones.

When cellphones and the internet first arrived, they didn’t have an immediate impact on society. After all, the internet was slow, not nearly everyone used it and most websites weren’t impressive.

These technologies simply couldn’t exist on the communications networks in place at the time. In response, engineers developed new networks to scale up the nascent technologies into what they are today. The networks they created were high-speed masterpieces made possible by advancements like the Viterbi Algorithm, which allowed us to communicate at near maximum capacity, known as the Shannon Limit.

Building a more reliable system

Today, engineers face a new problem: The systems we built for cellphones and the internet are suddenly not strong enough to reliably and efficiently transfer and process the type of data we’re working with. Trying to process data for machine learning leads to information bottlenecks. Relatively overnight, communication systems have turned into that old Roman aqueduct. And yet they are all we have.

That’s where Yu and coded computing come in. The latter clears up these system problems by applying coding theory, the backbone of the design for the original communication networks, to information systems. In fact, Qian developed a new field called “polynomial coded computing.” This approach uses such fundamental math that it can be applied to a wide set of computations (e.g., deep neural network training that is a workhorse of machine learning).

Polynomial coded computing essentially maps many large-scale distributed computing problems that underlie machine-learning algorithms to the problem of polynomial interpolation, adviser Avestimehr said.

“This mapping then allows us to leverage the rich set of tools and concepts developed in the coding and information theory literatures to develop fast, resilient, secure and private computing methods for machine-learning algorithms,” he said.