Quanquan C. Liu

quanquan AT mit DOT edu

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

Selected Papers (Show all)

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.