Quanquan C. Liu

MIT CSAIL
quanquan AT mit DOT edu

Research Interests:

graph algorithms, scheduling algorithms, parallel/distributed algorithms, dynamic algorithms and data structures, consensus, cache-efficient algorithms, proofs-of-space/memory/time

Google Scholar; DBLP; Github

About Me

I am currently a Postdoctoral Scholar at Northwestern University where I am very fortunate to be hosted by Samir Khuller. From September 2021-January 2022, I was a Postdoctoral Scholar at MIT where I had the pleasure of working with Julian Shun.

I graduated with my PhD in Computer Science from the MIT Theory Group where I was very fortunate to be 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 had the pleasure of being hosted by Joshua Wang. During the summer of 2019, I was a student researcher with the MIT Digital Currency Initiative where I was lucky to be hosted by Neha Narula and Tadge Dryja. I got my B.S. in Computer Science and Math where I had the honor of working with David R. Karger and MEng in Computer Science from MIT under the excellent mentorship of Erik D. Demaine.

Research Interests: graph algorithms, scheduling algorithms, parallel/distributed algorithms, dynamic algorithms and data structures, consensus, cache-efficient algorithms, proofs-of-space/memory/time

Papers

In chronological order; authors listed alphabetically (unless they're not).

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

Scheduling with Communication Delay in Near-Linear Time [arXiv] [Teaser] [Slides]
Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang in STACS 2022.
Invited to Special Issue of Springer Journal Theory of Computing Systems

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

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.

Parallel Batch-Dynamic k-Clique Counting [arXiv]
Laxman Dhulipala, Quanquan C. Liu, Julian Shun, and Shangdi Yu in APOCS 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]
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.

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.

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]

Preprints

A Lower Bound for Byzantine Agreement and Consensus for Adaptive Adversaries using VDFs [arXiv]
Thaddeus Dryja, Quanquan C. Liu, and Neha Narula

Parallel Algorithms for Small Subgraph Counting [arXiv]
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrović, and Ronitt Rubinfeld

Service

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, Transactions on Parallel and Distributed Systems

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.

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!