Hai sinh viên đại học giành giải thưởng Bài báo sinh viên xuất sắc nhất tại Hội nghị ACM

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).

Bùi Hồng Đức ( bên trái ) cựu HS trường Chuyên Khoa Học Tự Nhiên, Hà Nội trúng tuyển NUS ngành Computer Science năm 2021 đã xuất sắc giành được Học bổng Sea Olympiad.

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.

See more