Quanquan C. Liu

Northwestern University
quanquan AT mit DOT edu

About Me

I am currently a Research Fellow at the Simons Institute at UC Berkeley. Previously, I was a Postdoctoral Scholar at Northwestern University where I was advised by Samir Khuller and a Postdoctoral Scholar at MIT where I was advised by Julian Shun.

I graduated with my PhD in Computer Science from the MIT Theory Group where I was advised by Erik D. Demaine and Julian Shun. From June 2020 to December 2020, I was a Google Student Researcher with the IOR team in the Google Discrete Algorithms Group where I was advised by Joshua Wang. During the summer of 2019, I was a student researcher with the MIT Digital Currency Initiative where I was advised by Neha Narula and Tadge Dryja. I got my B.S. in Computer Science and Math at MIT where I was advised by David R. Karger and MEng in Computer Science from MIT where I was advised by Erik D. Demaine.

Research Interests: Theory and practice of algorithms for large data; dynamic, distributed, and parallel graph algorithms; algorithms and data structures; parallel and high performance computing; differential privacy and Byzantine-resilient algorithms

Papers (authors alphabetical unless not)

Scalable Auction Algorithms for Bipartite Maximum Matching Problems [arXiv][Slides]
Quanquan C. Liu, Yiduo Ke, and Samir Khuller, to appear in APPROX 2023.

An Algorithmic Approach to Address Course Enrollment Challenges [arXiv]
Arpita Biswas, Yiduo Ke, Samir Khuller, and Quanquan C. Liu in FORC 2023.

Triangle Counting with Local Edge Differential Privacy [arXiv]
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam Smith in ICALP 2023.

A Note on Improved Results for One Round Distributed Clique Listing [arXiv][Journal]
Quanquan C. Liu in Information Processing Letters 2023.

Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs [arXiv] [Slides] [FOCS Video] [Video]
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu in FOCS 2022.

Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems [arXiv][Slides][Code]
Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun in SPAA 2022.
Best Paper Award

Massively Parallel Algorithms for Small Subgraph Counting [arXiv][Slides][Video][Code]
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrović, and Ronitt Rubinfeld in APPROX 2022.

Scheduling with Communication Delay in Near-Linear Time [arXiv] [Short Video] [Slides] [Poster]
Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang in STACS 2022.
Invited to Special Issue

Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry-Breaking Problems [arXiv][Video][Slides]
Shiri Antaki, Quanquan C. Liu, and Shay Solomon in ITCS 2022.

Fully Dynamic $(\Delta + 1)$ -Coloring in Constant Update Time [arXiv] [Journal]
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, and Shay Solomon in ACM Transactions on Algorithms (TALG) 2022.

Chess Equilibrium Puzzles [Full Preprint][Publication]
Erik D. Demaine and Quanquan C. Liu in Mathematics Magazine 2023.

Parallel Batch-Dynamic k-Clique Counting [arXiv][Code]
Laxman Dhulipala, Quanquan C. Liu, Julian Shun, and Shangdi Yu in APOCS 2021.

The Power of Random Symmetry-Breaking in Nakamoto Consensus [arXiv]
Lili Su, Quanquan C. Liu, and Neha Narula in DISC 2021.

Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis [Proceedings]
Michael A. Bender, Rezaul Alam Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Helen Xu in SPAA 2020.

Tatamibari is NP-complete [arXiv]
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch in FUN 2020.

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class [arXiv][Poster][Slides]
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavalle, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel in ESA 2019.

Static-Memory-Hard Functions, and Modeling the Cost of Space vs. Time [ePrint][Slides][Code]
Thaddeus Dryja, Quanquan C. Liu, and Sunoo Park in TCC 2018.

Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity [Proceedings]
Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Helen Xu in SPAA 2018.

Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers [Proceedings][Slides]
Erik D. Demaine and Quanquan C. Liu in SPAA 2018.

Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy [arXiv]
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams in ITCS 2018.

Arboral satisfaction: recognition and LP approximation [Journal Publication]
Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, and Daniel Ziegler in Information Processing Letters Vol. 127, 2017.

Upward partitioned book embeddings [arXiv][Slides]
Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, and Quanquan C. Liu in GD 2017.

Inapproximability of the standard pebble game and hard to pebble graphs [arXiv] [Slides]
Erik D. Demaine and Quanquan C. Liu in WADS 2017.

Clickomania is hard, even with two colors and columns [Book Chapter]
Aviv Adler, Erik D. Demaine, Adam Hesterberg, Quanquan C. Liu, and Mikhail Rudoy in Mathematics of Various Entertaining Subjects Vol. 2, Princeton University Press, 2017.

Tangled Tangles [Book Chapter]
Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Quanquan C. Liu, Ron Taylor, and Ryuhei Uehara in Mathematics of Various Entertaining Subjects Vol. 2, Princeton University Press, 2017 and also in The Best Writing on Mathematics 2018.

Polylogarithmic fully retroactive priority queues via hierarchical checkpointing [Conference Proceedings] [Slides]
Erik D. Demaine, Tim Kaler, Quanquan C. Liu, Aaron Sidford, and Adam Yedidia in WADS 2015.

Kibitz: end-to-end recommendation system builder [Conference Proceedings]
Quanquan C. Liu and David R. Karger in RecSys 2015.

Thesis

Scalable and Efficient Graph Algorithms and Analysis Techniques for Modern Machines [Thesis] [Thesis Defense Slides]

Service

PC Membership: PPoPP 2023, ESA 2023, Highlights of Parallel Computing (HOPC) 2023, SPAA 2023, ALENEX 2022

Outside of research, I am a coach for the USA Computing Olympiad. Previous years' solutions can be found here! Allowed documentation for USACO (and IOI) contests can be found here.

I am a coach for Northwestern's ICPC team (news).

For the past two years, I've also been a trainer for the North America Programming Camp (NAPC).

I was a co-organizer for the A&C Seminar at MIT from Fall 2019-Spring 2021. Please email the new organizers on the new website if you want to give a talk!

I was a subreviewer for the following conferences: PODC 2017, ICALP 2018, ISAAC 2018, SODA 2019, SPAA 2019, PODC 2019, FOCS 2019, AFT 2019, ISAAC 2019, SODA 2020, SPAA 2020, STACS 2020, SWAT 2020, ICALP 2020, FOCS 2020, TCC 2020, SOSA 2021, SPAA 2021, ACDA 2021, ESA 2021, DISC 2021, Information and Computation Journal, ALENEX 2022, ITCS 2022, ICALP 2022, ESA 2022, SPAA 2022, SODA 2023, ICALP 2023, Transactions on Parallel and Distributed Systems

Miscellaneous

I had a blog (mostly about math and TCS---and some philosophy) during my undergrad days (with a few sporadic posts from recent times)!