Two undergraduate students win Best Student Paper Award at ACM Symposium

Bui Hong Duc and Shashwat Chandra have won the Best Student Paper Award at the 2024 ACM Symposium on Principles of Distributed Computing (PODC) in Nantes, France. Their award-winning paper, "Improved All-Pairs Approximate Shortest Paths in Congested Clique", is a joint work with Chang Yi-Jun, Michal Dory (Haifa University), and Dean Leitersdorf (former Research Fellow at NUS Computing).

The All-Pairs Shortest Paths (APSP) problem, which asks for the shortest paths between all pairs of nodes in a network, is a classical problem in graph theory and computer science. Efficiently solving APSP, particularly in large-scale networks, has numerous applications, including routing, network analysis, and transportation planning. This paper showed a major improvement in reducing the number of communication rounds required to compute approximate APSP in the Congested Clique model, a fundamental computational model in parallel computation. The improvement is achieved through new techniques for analysing and constructing hopsets, which add new connections to shorten the number of hops in shortest paths, and skeleton graphs, which are smaller graphs that approximately preserve distances.