Position: Postdoctoral Scholar
Current Institution: MIT
Abstract: Scalable and Efficient Graph Algorithms for Modern Machines
Rapidly growing real-world networks with billions of vertices call for scalable fast and efficient graph algorithms. Luckily commercial multi-core multi-processor and multi-machine environments can handle such volumes of data. Unfortunately despite the availability of such resources many current graph algorithms do not take full advantage of these parallel and distributed environments or have non-optimal theoretical guarantees translating to slower and less efficient algorithms in practice. The purpose of my research is to theoretically improve previous graph algorithms in modern machines. We demonstrate through experiments that such theoretical improvements also translate to practical gains. Towards this goal my research focuses on two aspects. First we formulate algorithms in computation models that mimic large-scale data processing environments. Algorithms in such models take advantage of clusters of machines and a machine’s multiple cores and processors. Second we use specific properties of real-world networks when designing our algorithms. The degeneracy is one such characteristic; while a network has billions of vertices its degeneracy may only be a few hundred. My past research includes both static and dynamic graph algorithms. My PhD thesis includes a variety of results in this area. Representation results include a new parallel level data structure for the k-core decomposition problem under batch-dynamic updates (where dynamic edge updates are applied in batches). We show that our data structure provably provides a (2+c)-approximation on the coreness of each vertex improving on the previously best-known bound of (4 + c) for any c > 0. We also formulated new parallel work-efficient batch-dynamic algorithms for triangle and clique counting. Our extensive experiments show orders of magnitude improvements in performance over the best previous implementations. In the future I hope to work on these and other problems with the overall goal of obtaining both theoretically and practically efficient graph algorithms that run on modern machines.
Bio:
Quanquan C. Liu recently received her PhD in EECS from MIT where she is currently a postdoctoral scholar. Her dissertation was advised by Erik D. Demaine and Julian Shun. Her current research focuses on parallel and distributed graph algorithms scheduling algorithms and dynamic algorithms/data structures. She has worked on a variety of problems in these domains including k-core decompositions subgraph counting maximal independent set (\Delta + 1)-coloring and near-linear time scheduling. Her other past research interests include cache-efficient and cache-adaptive algorithms and lower bounds consensus and memory-hard functions/proofs-of-space/proofs-of-memory. During the summer of 2020 she interned with Google’s discrete algorithms team as a student researcher working on various scheduling and routing algorithms research. Before that she was a summer research intern with the Digital Currency Initiative (with whom she is also currently a collaborator). She will be joining Northwestern’s CS theory group in February 2022 as a postdoctoral scholar.