Quanquan C. Liu
Yale University
quanquan DOT liu AT yale DOT edu
Google Scholar; DBLP;
Github
About Me
I am an assistant professor at Yale Computer Science. If you are a Yale student
interested in any of the topics I work on, please reach out via email.
I was a Apple Research Fellow at the Simons Institute at UC Berkeley during Fall 2023.
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
Current Group
Felix Zhou (PhD)
Pranay Mundra (PhD)
Jinghua Sun (Masters)
Teaching
CPSC 424: Parallel Programming Tools (see Canvas)
CPSC 202: Mathematical Tools for Computer Science (see Canvas)
CPSC 768: Scalable and Private Graph Algorithms
Papers
Note: Authors on papers in theoretical computer science are generally ordered alphabetically by last name.
Practical and Accurate Local Edge Differentially Private Graph Algorithms
[
arXiv]
Pranay Mundra,
Charalampos Papamanthou,
Julian Shun,
and
Quanquan C. Liu
to appear in
VLDB 2025.
The Power of Graph Sparsification in the Continual Release Model
[
arXiv][
Slides][
Video]
Alessandro Epasto,
Quanquan C. Liu,
Tamalika Mukherjee,
and
Felix Zhou
to appear in
RANDOM 2025.
Invited to Special Issue of TPDP 2024
The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations
[
arXiv][
Slides][
Video]
Quanquan C. Liu
and
Vaidehi Srinivas
in
COLT 2024.
Improved Massively Parallel Triangle Counting in O(1) Rounds
[
arXiv][
Slides]
Quanquan C. Liu
and
C. Seshadhri
in
PODC 2024 (Brief Announcement).
Fair Allocation of Conflicting Courses under Additive Utilities
[
Extended Abstract]
Arpita Biswas,
Yiduo Ke,
Samir Khuller,
and
Quanquan C. Liu
in
AAMAS 2024 (Extended Abstract).
Parallel k-Core Decomposition with Batched Updates and Asynchronous Reads
[
arXiv]
Quanquan C. Liu,
Julian Shun,
and
Igor Zablotchi
in
PPoPP 2024.
Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs
[
arXiv][
Slides]
Pattara Sukprasert,
Quanquan C. Liu,
Laxman Dhulipala,
and
Julian Shun
in
ALENEX 2024.
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 
-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.
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
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)!