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, approximation algorithms, cache-efficient algorithms, hardness of approximation, data structures and more.

Preprints

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 Nonlinear Space-Time Tradeoffs via Pebbling [ePrint]
with Thaddeus Dryja and Sunoo Park in TCC 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.

Service

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

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