Sidhanth Mohanty Wins Best Paper Award at FOCS 2025

Northwestern Engineering’s Sidhanth Mohanty earned a Best Paper Award at the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025) last month in Sydney.

Mohanty joined the McCormick School of Engineering as an assistant professor of computer science in September 2025.

The flagship conference of the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, FOCS covers a broad range of theoretical computer science, from algorithms and data structures to cryptography to quantum computing.

The winning paper, titled “Explicit Lossless Vertex Expanders,” is coauthored by Jun-Ting Hsieh (Carnegie Mellon University), Alexander Lubotzky (Weizmann Institute of Science), Assaf Reiner (Hebrew University of Jerusalem), and Rachel Yun Zhang (Massachusetts Institute of Technology). In the work, Mohanty explained, the team built an extremely well-connected network.

“Imagine a collection of nodes where each node is connected to only a small number of other nodes, but any small group of nodes still reaches out to a maximum number of other distinct nodes,” Mohanty said. “A random network has this ‘almost maximum outreach’ property, and the goal of the project was to give an explicit structured example of lossless vertex expansion without the use of randomness.”

Their findings demonstrate a fast, explicit approach to constructing highly connected-but-sparse networks with bonus structural properties.

“You can perform an efficient computation only on the name of the node, for example, and output exactly which other nodes it is connected to without having to store or scan the whole network,” Mohanty said.

When building a network at random, Mohanty said, researchers lacked an efficient way to verify strong connectivity in a particular random network. Instead of relying on an unreliable "pick one at random and check" method, the team aimed to prove a different kind of argument that guarantees the property by design.

“We expect the lossless vertex expansion techniques we developed to get around this verification barrier will also help researchers make progress on theoretical problems where the need for similar random-like objects arises, such as in cryptography, error-correcting codes, and data structures,” Mohanty said.

The team’s techniques, for instance, could be used to construct a quantum error-correcting code with a fast decoder.

“Fast decoding matters because in a future where quantum computers exist, we will need to detect and fix errors in real-time,” Mohanty said. “There is still much engineering needed to translate these theoretical designs to practical hardware-ready codes, but we see this as an encouraging step in the right direction.”

Professor Aravindan Vijayaraghavan underscored the central role of lossless expanders in a wide range of areas within computer science, communication, and signal processing, including error-correction, routing, randomness extraction, pseudorandomness and cryptography, quantum codes, and many topics in computational complexity theory.

“Lossless expanders are incredibly useful objects in modern computing,” said Vijayaraghavan, associate professor of computer science and (by courtesy) industrial engineering and management sciences. “Sidhanth's research resolves the outstanding question of constructing explicit lossless expanders—a challenge that had been open for several decades. We are thrilled that he joined the Northwestern faculty last year and look forward to more breakthroughs from Sidhanth and his group.”