Welcome to Quantum Magazine's podcast.

Each episode we bring you stories about developments in science and mathematics.

I'm Susan Vallett.

A team of computer scientists has come up with a dramatically faster algorithm for one of the oldest problems in computer science, maximum flow.

That's next.

Explore science mysteries in the Quanta book, Alice and Bob meet the Wall of Fire,

published by the MIT Press.

Available now at Amazon.com, Barnes & Noble.com, or your local

bookstore. The maximum flow problem asks how much material can flow through a network

from a source to a destination if the links in the network have capacity limits. Daniel Spielman is a

mathematics and computer science professor at Yale University. It's absurdly fast. I mean, it's

nearly linear time. There was no good reason to believe we could do that. Like, there'd been a lot of

advances made in the last 15 years in the running

time of this algorithm. And we seem to be stuck at a particular running time. And I was actually

inclined to believe that was an actual limit, like that we weren't going to do better. So I

turned to believing that algorithms is good for this problem did not exist. To me, it's really exciting to do better. So I turn to believing that algorithms is good for this problem

would not exist. To me, it's really exciting to say it.

Maximum Flow has been studied since the 1950s when it was formulated to study the Soviet

railway system. Edith Cohen is with Google research in Mountain View, California.

This is an extremely basic problem on graphs.

It had been around much more than many things. It's older than maybe the theory of computer

science in some sense. The problem has many applications, internet data flow, airline

...