A guide to events on our campuses.

Assembly Series

A tradition of convening thought leaders since 1953

McKelvey School of Engineering

Brown School

Scalable Graph Algorithms: Parallel, Dynamic, and Private

Monday, March 20 | 11:30 AM

McKelvey 1020

Quanquan Liu

Postdoctoral Scholar 

Department of Computer Science

Northwestern University 

Graph algorithms are ubiquitous in today’s world where graph analytics are performed over massive datasets containing potentially sensitive information. Modern graphs present many new challenges not considered by classic static, sequential computation models. First, graphs have up to trillions of edges and are several orders of magnitude larger than what traditional sequential algorithms can handle. In addition to scale, modern graphs are also dynamically evolving with up to millions of changes per second. Second, data leaks and commercial data trading threaten to expose the large volume of sensitive private information contained in these graphs. Third, the monetary and resource incentives associated with large distributed graphs (e.g., for cryptocurrency) make them vulnerable to malicious adversaries. Thus, modern graph algorithms must achieve several simultaneous goals: efficiency, scalability, privacy, and robustness against adversaries.

In this talk, I will present algorithms that rise to these aforementioned challenges. I will first present novel scalable algorithms for k-core decomposition and related important problems in computational models that take advantage of modern parallel computing architectures and dynamic environments. These algorithms not only achieve theoretical improvements but also hundreds of times speedups over the state-of-the-art in practice. Then, I will formalize models and give algorithms that combat broader societal concerns of privacy breaches and susceptibility to adversarial attacks. Finally, I’ll discuss my broader research vision in combining scalability with adversary-robustness.  

Event Type



McKelvey School of Engineering


Science & Technology

Computer Science & Engineering
Event Contact


Speaker Information

Quanquan C. Liu is a postdoctoral scholar at Northwestern University advised by Samir Khuller. She completed her PhD in Computer Science at MIT where she was advised by Erik D. Demaine and Julian Shun. Before that, she obtained her dual bachelor’s degree in computer science and math also at MIT. She has worked on a number of problems in algorithms and the intersection between theory and practice. Her most recent work focuses on parallel dynamic and static graph algorithms as well as differentially private graph algorithms. She has earned the Best Paper Award at SPAA 2022, a NSF Graduate Research Fellowship, and participated in the 2021 EECS Rising Stars workshop.

Google Calendar iCal Outlook