Qian with his recently proposed Lagrange coded computing design, which provides optimal resiliency, security and privacy for distributed computing systems. Photo Credit: USC Viterbi
The Pont du Gard is one of the most famous aqueducts of the Roman empire. The two-thousand-year-old masterpiece is a triple-level aqueduct that stands 161 feet high, is nearly a kilometer long, and provided water to the 60,000 citizens of Nimes in southern France. Still standing today, it’s so well known that when you google image search “aqueduct” it’s the first thing you see.
Now, imagine that overnight, the city grew to a population of a million. How would you use this suddenly less-than-ideal piece of technology to get water safely to everyone?
This is the type of question that Qian Yu, a PhD student in the Ming Hsieh Department of Electrical Engineering asks himself every day. Only instead of building aqueducts, he is an expert in Coded Computing – a field so new it was developed right here at USC Viterbi in the lab of Salman Avestimehr, Yu’s advisor.
Today, engineers are facing a new problem: The systems we built for cell phones and the internet are suddenly not strong enough to reliably and efficiently transfer and process the type of data we’re working with.
For his efforts, Yu was recently named the winner of a 2018 Google Fellowship in machine learning. So, what is Coded Computing and why is it so important? To understand his work and its impact we have to go back in time, to the early days of the internet and cell phones. So, make sure no one is talking on the house line, switch on that sweet 56K dial-up modem, and let’s get started.
When cell phones and the internet first arrived, they didn’t immediately have the impact on society that they do today. Think about why today’s phones are called “smart” phones? It’s because their predecessors were…not so much.
These technologies simply couldn’t exist on the communications networks we already had in place. In response, engineers developed new networks to scale up these 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).
Today, engineers are facing a new problem: The systems we built for cell phones 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, a hugely important new tool, leads to information bottlenecks and even a failure for the correct information to reach its destination. Relatively overnight, our communication systems have tuned into that Roman aqueduct. And yet, they are all we have.
That’s where Yu and Coded Computing come in. Coded Computing clears up these system problems by applying coding theory, which was the backbone of the design for 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 very wide set of computations (e.g., deep neural network training that is a workhorse of machine-learning).
Qian (right) with his advisor, Salman Avestimehr. The two, along with other researchers, created the field of Coded Computing. Photo Credit: USC Viterbi
“Polynomial coded computing essentially maps many large-scale distributed computing problems that underlie machine-learning algorithms to the problem of polynomial interpolation,” says Avestimehr. “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.”
In other words, Yu’s math has found a way for that outdated Roman aqueduct to do a job it was never built to do. And his math is so fundamental that it can be used to do even more than one new thing. It not only increases the efficiency of systems, it makes them more secure and private too. It’s actually like he’s found a way for that old aqueduct to provide more water, and clean the water, and mineralize it too!
Winning awards for transformative math is nothing new for Yu. Last year, he won the Jack K. Wolf Student Paper award at the International Symposium of Information Theory for solving a 5-year open problem related to communications. He will receive that award in June of this year.
Decades ago, the Viterbi algorithm was created right here at the Ming Hsieh Department of Electrical Engineering to scale up cell phones and the internet and make them essential tools of the modern world. Today, Coded Computing, another creation from the very same department, is doing the same thing for Machine Learning.
Published on June 12th, 2018
Last updated on April 8th, 2021
