ARC Seminar: Quanquan C. Liu (MIT)

ARC Seminar

Quanquan C. Liu (MIT)

Wednesday, March 31, 2021

Virtual via Bluejeans - 11:00 am


Title:  Parallel Algorithms for Graph Computations

Abstract:  Parallel algorithms are often used in practice for their concrete speed-ups compared to standard sequential algorithms in today's data processing architecture. Algorithms for problems such as triangle counting and k-core decompositions are used in applications such graph visualization, community detection, and graph clustering algorithms. In this talk, I will discuss several novel parallel algorithms for graph computations (in both the static and dynamic settings) that operate in the work-depth (the standard model for shared-memory multicore systems) and the massively parallel computation (MPC) model (the standard for large-scale multi-machine distributed architectures). I will discuss in detail two specific algorithms. In the static setting, I will discuss a O(log log n)-round MPC algorithm that exactly counts the number of triangles and performs in O(n^{\delta}) (for any constant \delta) space per machine, and total space O(m \alpha) where \alpha is the arboricity of the graph. 

In the dynamic, work-depth setting, I will talk about some very recent work on parallel (2+\epsilon)-approximate k-core decompositions, a central subroutine in many different types of applications. All discussed algorithms improve upon the theoretical guarantees of previous work. In addition, we implemented all algorithms under experimental settings and found they exhibit improved performances compared to previous implementations on graphs obtained from the Stanford Large Network Dataset Collection (SNAP). I will conclude with some interesting future work.


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Wednesday, March 31, 2021
    12:00 pm - 1:00 pm