Laxman Dhulipala Honored with Allen Newell Award for Research Excellence

Laxman Dhulipala, an assistant professor of computer science at the University of Maryland, was part of a team recently honored with the prestigious Allen Newell Award for Research Excellence for their breakthroughs in large-scale graph processing.

The award is from Carnegie Mellon University’s (CMU) School of Computer Science. It recognizes outstanding work from current or former CMU researchers that epitomizes the scientific philosophy of Allen Newell, a computer scientist and pioneer in the field of artificial intelligence who died in 1992.

Newell firmly believed that “good science responds to real phenomena or real problems.”

Dhulipala, who also has an appointment in the University of Maryland Institute for Advanced Computer Studies, was recognized with the Newell award for work he did as an undergraduate student at CMU. He went on to receive his doctorate in computer science from CMU in 2020.

In 2013, Dhulipala was part of a team that began to explore how to analyze huge graphs on relatively inexpensive shared memory multiprocessors. They built a sequence of frameworks—known as Ligra, Ligra+, Julienne, GBBS, Aspen, and Sage—which makes it much easier for programmers to efficiently solve a wide variety of graph problems.

According to a nomination letter by Daniel Sleator, a professor of computer science at CMU, the team obtained “many truly outstanding results” in which their provably efficient algorithms running on an inexpensive machine are faster than any prior algorithms, even those running on much bigger and more expensive machines. Examples of such results include clustering, clique counting, and various forms of connectivity.

In addition to having a tremendous impact on research in the field, their ideas are being used in industry to handle real-world problems. For example, at Google their foundational work is being used to cluster very large graph datasets an order of magnitude faster than the previously-used distributed approaches based on MapReduce-style systems.

Dhulipala collaborated on the project with Julian Shun, who received his doctorate from CMU and is now an associate professor of electrical engineering and computer science at the Massachusetts Institute of Technology, and Guy Blelloch, a professor of computer science at CMU who advised both Dhulipala and Shun.

The trio was recently formally recognized with the Newell award at CMU’s Founders Day event.

—Story by Melissa Brachfeld, UMIACS communications group