Quanquan C. Liu

quanquan AT mit DOT edu

I am a PhD student in the MIT Theory Group, where I am very fortunate to be advised by Erik D. Demaine. I got my B.S. in CS/Math and MEng in Computer Science from MIT.

My research interests include graph algorithms (both in the sequential and parallel/distributed sense), approximation algorithms, cache-efficient algorithms, proofs of space/work, memory-hard functions and more.

I am co-organizing 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!

Links: CV (updated Dec. 2018), DBLP, Google Scholar


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

Selected Papers (Show all)

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.

Tangled Tangles [Book Chapter]
with Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Ron Taylor, and Ryuhei Uehara in Mathematics of Various Entertaining Subjects Vol. 2.

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.


I was a subreviewer for the following conferences: PODC 2017, ICALP 2018, ISAAC 2018, SODA 2019, SPAA 2019.

Outside of research, I am a coach for the USA Computing Olympiad.