Speaker:Yan Gu, Assistant Professor of Computer Science and Engineering, UCRiverside

Abstract:This talk will mainly cover two categories of our recent work on parallel algorithms. I will first introduce our new algorithms for computing shortest paths. I will cover the two simple yet efficient algorithms, the rho-stepping and the delta*-stepping algorithms, for computing single-source shortest paths (SSSP). Then I will talk about some of our ongoing work on computing s-t (pairwise) shortest paths and contraction hierarchies. The second part of this talk will introduce a list of our recent work on parallelizing work-efficient dynamic programming algorithms. Dynamic programming is one of the most studied algorithmic techniques and has been highly optimized sequentially using optimizations such as sparsification and monotonicity. However, how to apply such optimizations in parallel remained unknown until recently. I will show a general framework that can parallelize these optimized sequential algorithms. Finally, if time permits, I will briefly cover some of our recent work on nearest-neighbor search.

Speaker Bio:Yan Gu is an Assistant Professor in the Computer Science and Engineering (CSE) Department at UC Riverside. He finished his PhD degree at Carnegie Mellon University in 2018, and his Bachelor's degree from Tsinghua University in 2012. Before joining UCR, he spent one year as a postdoc at MIT. His research interest is 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, and haswonthe Best Paper Awards atPPoPP'23andESA'23, the Best Paper Runner-up in VLDB'23, and the Distinguished Paper Award of SPAA'20.