algorithms
13 December 2021
As the first Dane, Professor Mikkel Thorup receives the prestigious Fulkerson Prize
Algorithms
The Fulkerson Prize goes to the most famous research results in discrete mathematics, which is the branch of mathematics most relevant to computer science and data science. Professor Mikkel Thorup is the first Dane ever to be awarded the prize for finding the solution to a problem that it took him 18 years to figure out.
It takes time, perseverance, and patience to solve the kind of mathematical problems that algorithmics deals with – and preferably change of air along the way.
- It's like hiking an unknown mountain terrain. You may have an idea of a possible path to a particular peak, but then the path turns out to be cut off by deep ravines. While you are out there, you must constantly be creative and seek new paths. You must also be flexible because you often discover other peaks that are worth visiting, says Professor Mikkel Thorup.
The problem he has solved is about edge connectivity of a network which is one of the most fundamental problems of graph theory. It's about figuring out how many edges you can remove from a network before it breaks.
After 15 years in the United States, a move back to Denmark, and finally a trip to Japan, where Mikkel Thorup visited the Japanese co-author, Professor Ken-Ichi Kawarabayashi, and took countless walks around the Imperial Palace in Tokyo, the big breakthrough came:
An efficient algorithm that finds the edge connectivity of a network completely without the use of randomness; that is, an algorithm that can guarantee its answers one hundred percent. The result was published in 2018 in the Journal of the ACM.
- During my 15 years as a leading industrial researcher at AT&T Laboratories, the solution to this problem was always at the top of my wish list. Networks exist in all sorts of places, for example as road networks and social media. When you have a large network, you want an efficient algorithm that can quickly figure out the edge connectivity; that is, how close the network is to breaking down, Mikkel Thorup explains.
Long-lasting influence on the field
The problem of edge connectivity has been researched since 1961. Mikkel Thorup himself became interested in the problem when he was a visiting researcher at the Massachusetts Institute of Technology (MIT) in 1997.
A famous professor from MIT, David Karger, had in 1996 presented an effective solution to the problem, but his breakthrough was a randomized algorithm that uses randomness. This means that one can never be one hundred percent sure whether Karger's algorithm gives the correct answer.
Although Karger's algorithm says that the network is well connected, it may be about to fall apart. Karger's big unsolved problem was to find an efficient algorithm that did not use randomness so that one can rely one hundred percent on the answer.
The American Mathematical Society (AMS), which is the world's largest mathematics community and is responsible for awarding the Fulkerson Prize together with the Mathematical Optimization Society (MOS), writes the following about Mikkel Thorup's and Ken-Ichi Kawarabayashi's solution:
- This work does not just improve the running time of the algorithm, impressive as that is. Its main contributions are conceptual: the paper introduces powerful and impactful new ideas that will have a long-lasting influence on the field.
Read the full statement from AMS here.
Mikkel Thorup and Ken-Ichi Kawarabayashi's theoretical breakthrough has inspired further research in the field, and in December 2021 the article had already been cited 87 times.
Understand the edge connectivity problem
The problem is about how well a network is connected. A network has some knots and some edges that connect them. These networks (also called graphs) appear in many places. They can be road networks where the edges are roads, and the knots are crossroads. They can also be social networks, for example, Facebook, where the knots are people with edges to their friends.
When you have such a network, you can ask how many edges you need to remove for it to break. This is called the network’s edge connectivity. The blue graph below has edge connectivity 2 because it will break if we remove the two edges that cross the red line.
About the Fulkerson Prize
The Fulkerson Prize is named after the pioneer Delbert Ray Fulkerson (1924-1976) who co-developed the Ford-Fulkerson algorithm, one of the most well-known algorithms to solve the maximum flow problem in networks.
The prize is awarded every three years since 1979 to the most significant scientific articles in discrete mathematics, including algorithmics and graph theory, at the crossroads between mathematics and computer science. Previous years' prizes have been awarded to both pure mathematical articles and articles from computer science.
Within computer science, the prize has been awarded for famous results such as Leonid Khachiyan's polynomial algorithm in linear programming from 1979 and Manindra Agrawals, Neeraj Kayals, and Nitin Saxena's result on "PRIMES is in P" from 2006.
Among the well-known mathematical results are Kenneth Appels and Wolfgang Haken's article on four colorable planar maps from 1977 and Thomas Hales' article on Kepler's conjecture from 2005.
About Mikkel Thorup
Mikkel Thorup is one of the world's leading experts in algorithms and data structures. He is originally a graduate engineer from the Technical University of Denmark and holds a PhD from Oxford University.
From 1998 to 2013, he worked as a leading industrial researcher at the world-renowned American telecommunications and research giant AT&T Bell Labs, which owns much of the Internet and leases virtual networks to large companies such as IBM and General Motors. Here, Mikkel Thorup obtained 18 patents, published more than 100 scientific articles, and was bestowed the AT&T Fellows Honor.
Since 2013, Mikkel Thorup has been a Full Professor at the Department of Computer Science at the University of Copenhagen. He is currently head of the research section Algorithms and Complexity and head of the BARC centre (Basic Algorithms Research Copenhagen). The centre’s researchers have repeatedly made mathematical breakthroughs. According to CSRankings for 2021, the University of Copenhagen is in fourth place of the best universities in the world, measured by the number of top articles in algorithmics.
In 2015, Mikkel Thorup received Denmark's largest individual researcher award, Villum Kann Rasmussen's Annual Scholarship for Technical and Scientific Research of DKK 5 million. Mikkel Thorup has also received several other prestigious awards, including an MAA Robbins Prize in Mathematics, and Fellow of the ACM in Computer Science. In addition to the Fulkerson Award, he has also recently received a 20-Year STOC Test of Time Award.
Contact
Mikkel Thorup
Professor, Department of Computer Science
Head of the Algorithms and Complexity section and Head of the BARC centre
mthorup@di.ku.dk
Caroline Wistoft
Communications consultant, Department of Computer Science
cawi@di.ku.dk