Quanquan C. Liu

quanquan AT mit DOT edu

About Me

I am a PhD student in the MIT Theory Group where I am 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.

I am also a co-organizer for the A&C Seminar at MIT this year. Please email me or any of the other organizers on the website if you want to give a talk!

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


In chronological order; all authors alphabetical as standard in TCS.

Parallel Batch-Dynamic k-Clique Counting [arXiv]
with Laxman Dhulipala, Julian Shun, and Shangdi Yu to appear in APOCS 2021.

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

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

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class [arXiv][Poster][Slides]
with Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavalle, 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]
with Thaddeus Dryja and Sunoo Park in TCC 2018.

Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity [Proceedings]
with Andrea Lincoln, 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]
with Erik D. Demaine in SPAA 2018.

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

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

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

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

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

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

Kibitz: end-to-end recommendation system builder [Conference Proceedings]
with David R. Karger in RecSys 2015.


Parallel Batch-Dynamic k-Core Decomposition [arXiv]
with Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun

Dynamic Distributed MIS with Improved Bounds [arXiv]
with Shiri Antaki, and Shay Solomon

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

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

Fully Dynamic (\Delta + 1)-Coloring in Constant Update Time [arXiv]
with Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, and Shay Solomon


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 2020

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.