In the Geometric, Approximation and Distributed Algorithms (GADA) lab, a theoretical approach to computer science problems is taken. While often the image that comes to mind with computer science is coding, undergraduate student researcher Atishaya Maharjan said that in the GADA lab, that is not always the case. “The only utensils we normally use [are] a whiteboard and our brains,” Maharjan said.
In the lab, computer science questions are answered mathematically through designing algorithms and writing proofs. The aim of this approach is to create algorithms that work consistently and efficiently.
The lab is led by Stephane Durocher, a U of M professor of computer science, along with associate professor Ben Li, associate professor Avery Miller, assistant professor Anurag Murty Naredla and assistant professor Leqi (Jimmy) Zhu. Currently, eight graduate students and post-doctoral students work in the GADA lab, along with additional undergraduate student researchers.
The GADA lab is a popular computer science lab for student researchers, due to its collaborative nature. Interested computer science students are invited to attend weekly meetings between researchers, where they can experience work in a low-stakes environment. “We try to make it supportive and welcoming to students,” Durocher said. “It’s not a place where you necessarily have to feel like, ‘I don’t know anything about this stuff, I shouldn’t be here.’”
This support and collaboration is something that Maharjan valued about the GADA lab. “Although we weren’t working on the same problems […] you could still get updated,” Maharjan said. “If you have any ideas on [others’ problems], you could also jump in [and] collaborate, ” he added.
Maharjan has completed three summer terms with the lab. During his first year, he worked to build an algorithm that minimized interference in wireless networks. The following year he studied the Wiener index, which, in a network, measures the entire distance between pairs of points. For this work, he developed and tested an algorithm that broke down the task of optimally connecting points into smaller pieces and integrated the solutions. This past year, his area of focus was one that he found personally the most engaging. It focused on how drones can work together to most fuel-efficiently deliver a package. “The goal is to determine which drones should carry it and where they should hand it off to minimize total fuel use,” Maharjan said.
Keira Pasveer, an undergraduate student researcher with the GADA lab, said in the lab she relied primarily on her math background. “I didn’t end up doing any coding at all,” Pasveer said. This past summer, Pasveer worked with Zhu to apply geometry to a discrete Voronoi game. This game is structured with two competing opponents. “Think of the players as grocery store owners,” said Pasveer. Each player takes turns building stores in the most population-dense locations. The winner is the player that has the most customers at their store.
Pasveer’s research focused on creating an algorithm and proof to determine who will win. Up until this point, the only study on this subject had been able to prove that if player two builds one store, to win, player one must build five or more stores. In their research, Pasveer and Zhu were able to prove that player one could win with only three stores, if the stores were in a specific arrangement.
The time it takes to solve a problem varies widely. “Sometimes you get together with some other researchers […] and you can solve a problem in a couple days,” said Durocher. “Other times it takes years.” Durocher highlighted two problems he is currently working on with collaborators, both concerning geometric optimization. In the first problem he is exploring the most efficient way of dividing a polygon evenly, where the cut goes from vertex to vertex, with PhD student Amirhossein Mashghdoust. The second problem concerns the possibility of creating an algorithm that connects points in a plane where Durocher said “every vertex has at most three edges adjacent to it and no two edges cross.” For this question, Durocher must either prove it is not possible by creating a counter example, or he must successfully create an algorithm to prove that it is possible.
Durocher understands the value of undergraduate research goes beyond its application to his work. “It’s not just about us as researchers trying to get publications, it’s really about the students,” Durocher said. For him, his interest in theoretical computer science was sparked by a university class he took during his undergraduate degree and a subsequent research assistant role. Durocher encouraged students to seek out research positions in their undergraduate studies. “It gives you a very good idea of what would be involved in doing research as a graduate student,” he said.
Artificial intelligence (AI) is changing research in theoretical computer science. “When you read in the news about […] some AI company solving these big questions in math,” Durocher said, “they’re also solving important questions in theoretical computer science.”
The typical process of creating and validating research in this field has been disrupted. “AI has allowed people to submit a thousand times more papers as they used to,” Durocher added. This has proved to be problematic for scientific journals. “AI generates stuff much faster than humans can consume it,” he noted. While these papers can be verified and deemed correct through proof checkers, Durocher shared he is critical of these findings. “No human, or very few humans can sit down and actually understand what is in the paper,” he said.
The way forward for the field is unclear, but Durocher does not think humans should be taken out of the process. “We need humans who can solve problems. That’s not going away,” Durocher said.




