How Randomness Tames Vast Network Problems
- Theoretical computer scientist Rasmus Kyng and his research group are tackling massive network problems—such as matching ride-hailing passengers with drivers or distributing computing tasks across servers—by developing advanced...
- Think internet computer connections, power grids, and transportation routes.
- Many networks, including power grids and the distribution of heat in buildings, rely mathematically on Laplacian equations.
Theoretical computer scientist Rasmus Kyng and his research group are tackling massive network problems—such as matching ride-hailing passengers with drivers or distributing computing tasks across servers—by developing advanced mathematical solvers.
Mapping the Complex Architecture of Modern Networks
Networks underpin critical modern infrastructure. Think internet computer connections, power grids, and transportation routes. Yet complex challenges that initially seem unrelated to networks can be effectively modeled and solved as network problems.
Confronting the Computational Bottleneck of Laplacian Equations
Many networks, including power grids and the distribution of heat in buildings, rely mathematically on Laplacian equations. These same equations are vital for artificial intelligence and machine learning applications.
However, scale remains a massive hurdle. When networks expand to millions or billions of connections, traditional solving methods demand excessive time and memory, rendering them impractical at this scale.
To combat this, Kyng collaborates with former student Yuan Gao and doctoral supervisor Daniel Spielman. The team recently detailed a novel solver for Laplacian equations in the SIAM Journal on Scientific Computing. Early prototypes demonstrate that this new software runs reliably and substantially faster than existing tools across diverse test cases.
Rasmus KyngThe results show that methods developed in theoretical computer science can become practical tools for solving very large network problems.
Translating Abstract Mathematics Into Linear-Time Algorithms
Kyng’s research follows a two-stage research process to transition abstract mathematics into functional software for supercomputers.
The first stage addresses core mathematical questions, specifically whether an algorithm can solve a problem while keeping computational cost growth moderate as the problem becomes larger. Ideally, if a network scales up tenfold, computational effort should rise by roughly that same factor. In reality, computational demands often surge much faster. Kyng focuses heavily on crafting nearly linear running time algorithms that scale efficiently.
Honors, Data Reduction, and Production-Ready Software
For his scientific work on highly efficient algorithms, Kyng was awarded the 2025 ETH Zurich Latsis Prize. His work also explores which information a computation can ignore without losing accuracy.
The second stage bridges theory and reality by transforming theoretical insights into practical software. This phase strips away excess theoretical machinery, isolating the core mechanisms responsible for speed enhancements and adapting them to work on a real computer.