UMD Team Wins Prestigious Best Paper Award for Solving 35-Year Mathematical Puzzle

A University of Maryland research team has earned the Best Paper Award at the 66th IEEE Symposium on Foundations of Computer Science (FOCS), one of the oldest and most prestigious conferences in computer science, for solving a mathematical problem that had remained open for 35 years.

Led by Mohammad Hajiaghayi, the Jack and Rita G. Minker Professor of Computer Science, the team tackled the long-standing Steiner Forest problem, a cornerstone challenge in network design. The problem asks how to connect pairs of points in a network using the least possible total cost, essentially finding the most efficient way to link specific pairs of nodes while minimizing the number of edges needed.

“It’s a very fundamental problem in computer science and mathematics,” Hajiaghayi said. “It has deep implications for how we design efficient systems, from communication networks to modern AI chips.”

The research was conducted by Hajiaghayi and four of his doctoral students—Ali Ahmadi, Iman Gholami, Peyman Jabbarzade and Mohammad Mahdavi—all International Olympiad in Informatics medalists. Together, they spent three years developing new algorithms that broke through the “2-approximation” barrier that had limited solutions since 1989. Their 126-page paper combines several novel algorithmic techniques and offers new structural insights into the problem.

Jabbarzade said the team’s success stemmed from persistence and collaboration. 

“We worked dedicatedly to design multiple algorithms, each interesting on its own and with potential applications to other problems,” he said. “By combining these algorithms and carefully analyzing them, we were able to break the long-standing barrier of 2 for the Steiner Forest problem. I’m thrilled that the community recognized this progress with the FOCS Best Paper Award. It’s very motivating and reinforces the value of pursuing deeper structural understanding in classical problems.”

The team’s work has broad implications, particularly for chip design. Modern GPUs and AI accelerators, such as those made by Nvidia and Google, rely on connecting millions of tiny transistors. More efficient wiring can reduce energy use, cost and heat production, ultimately improving chip performance.

“When you design an AI chip, each transistor needs to connect to others, and the total wiring length affects performance,” Hajiaghayi explained. “Our algorithms can help identify shorter, more efficient connections, which translates into faster and more energy-efficient hardware.”

The FOCS award highlights the importance of the work. Founded in 1959, the conference has historically recognized only one or two papers each year for outstanding contributions to theoretical computer science. Hajiaghayi noted that this recognition is especially meaningful because the research was conducted entirely in Maryland.

“This was a completely UMD effort, just me and my students,” he said. “That shows the exceptional caliber of our graduate students and the kind of research we can achieve here.”

—Story by Samuel Malede Zewdu, CS Communications