Colloquium - Yan Gu, "Recent Advances in Parallel Algorithm Design"

Abstract: 
This talk will focus on two main categories of our recent advancements in parallel algorithms. In the first part, I will introduce our new graph algorithms with an emphasis on computing shortest paths. I will discuss two simple yet highly efficient algorithms for single-source shortest paths (SSSP): the rho-stepping and delta*-stepping algorithms. Additionally, I will provide an overview of our ongoing research on pairwise shortest paths (s-t paths) and contraction hierarchies. 

The second part of the talk will delve into our decade-long research in parallelizing sequential iterative algorithms, such as greedy algorithms and dynamic programming. The core concept here is to identify the inherent computational structures and develop a general framework for their parallel execution. I will briefly discuss applications such as random permutation, maximal independent set (MIS), and strongly connected components (SCC). Then I will focus on a recent framework for parallelizing dynamic programming algorithms (SPAA'24 Outstanding Paper).

Bio:
Yan Gu is an Assistant Professor in the Computer Science and Engineering (CSE) Department at UC Riverside. He completed his PhD at Carnegie Mellon University in 2018 and his Bachelor’s degree at Tsinghua University in 2012. Before joining UCR, he spent one year as a postdoc at MIT. His research interest lies in designing simple and efficient algorithms with strong theoretical guarantees and good practical performance. He is a recipient of the NSF CAREER Award and the Google Research Scholar Program in 2024. He has won the Best Paper Awards at PPoPP'23 and ESA'23, the Best Paper Runner-up at VLDB'23, and the Outstanding Paper Awards at SPAA'24 and SPAA'20.