Speaker:Nairen Cao

Title 

Efficient Parallel Algorithms for Large-scale Graphs

Abstract

In today's big data era, processing large-scale graphs, especially those with millions of nodes, presents formidable challenges. Traditional sequential algorithms often fall short in efficiency, making the shift toward parallel or distributed algorithms essential. My research contributes to this field by developing efficient parallel algorithms that address these challenges. In this talk, I will highlight two major areas of my work:
1. Single-source Shortest Path (SSSP): I will explore our approach to the SSSP problem in large graphs. We will delve into our methods for both approximate and exact solutions across various graph conditions with different edge weights. Our techniques mark a significant improvement in the parallel setting, offering an innovative method for tackling this classic problem.
2. Correlation Clustering: I will present our development of a highly efficient parallel algorithm for the Correlation Clustering problem. This approach achieves a notable approximation ratio while maintaining reasonable computational work and depth. In addition, I will discuss our groundbreaking approach in the sequential setting, which not only simplifies the process but also achieves a state-of-the-art approximate ratio.

About Nairen Cao

Nairen Cao is a Postdoctoral Researcher at Boston College. His research primarily focuses on developing efficient (usually parallel) algorithms, particularly for graph problems. He obtained his PhD from Georgetown University in August 2022. His work was nominated as Outstanding Papers at the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2022 and 2023.