Allen Liu

I am an Assistant Professor of Computer Science at NYU Courant. I have worked broadly in algorithms and machine learning theory. Currently, my main interest is in foundations of machine learning and language models. I have also worked on areas ranging from fundamental computational and statistical questions to inverse problems in the sciences, especially in quantum information.

Previously I was a Miller postdoctoral fellow at UC Berkeley in fall 2025, hosted by Prasad Raghavendra and I completed my PhD in EECS at MIT where I was fortunate to be advised by Ankur Moitra. My work was supported by an NSF Graduate Research Fellowship, a Hertz Fellowship, and a Citadel GQS Fellowship. I also completed my undergraduate degree (in mathematics) at MIT.

Email: cliu568 at gmail dot com

Publications

In my field, author order is generally alphabetical by last name

Sequences of Logits Reveal the Low Rank Structure of Language Models
Noah Golowich, Allen Liu, Abhishek Shetty
Manuscript

Provably Extracting the Features from a General Superposition
Allen Liu
Manuscript

Provably Learning from Modern Language Models via Low Logit Rank
Noah Golowich, Allen Liu, Abhishek Shetty
Manuscript

Model Stealing for Any Low-Rank Language Model
Allen Liu, Ankur Moitra
STOC 2025

Learning the closest product state
Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, Ewin Tang
QIP 2025 Short Plenary, STOC 2025

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang
QIP 2025 Invited Plenary, FOCS 2024, Quanta

Structure learning of Hamiltonians from real-time evolution
Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang
FOCS 2024

Learning Quantum Hamiltonians at any Temperature in Polynomial Time
Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang
QIP 2024 Invited Plenary, Best Student Paper, STOC 2024, Quanta

An Optimal Tradeoff between Entanglement and Copy Complexity for Quantum State Tomography
Sitan Chen, Jerry Li, Allen Liu
STOC 2024

Constant Approximation for Individual Preference Stable Clustering
Anders Aamand, Justin Y. Chen, Allen Liu, Sandeep Silwal, Pattara Sukprasert, Ali Vakilian, Fred Zhang
NeurIPS 2023, Spotlight

When Does Adaptivity Help for Quantum State Learning?
Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke
FOCS 2023

Matrix Completion in Almost-Verification Time
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
FOCS 2023

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan
FOCS 2023, Invited to SIAM Journal on Computing Special Issue

Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
COLT 2023

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau
ICML 2023

A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau
STOC 2023

Robust Voting Rules from Algorithmic Robust Statistics
Allen Liu, Ankur Moitra
SODA 2023

Robust Model Selection and Nearly-Proper Learning for GMMs
Jerry Li, Allen Liu, Ankur Moitra
NeurIPS 2022

Tight Bounds for Quantum State Certification with Incoherent Measurements
Sitan Chen, Brice Huang, Jerry Li, Allen Liu
QIP 2022, FOCS 2022

Minimax Rates for Robust Community Detection
Allen Liu, Ankur Moitra
FOCS 2022

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication
Allen Liu, Mark Sellke
COLT 2022

Learning GMMs with Nearly Optimal Robustness Guarantees
Allen Liu,Ankur Moitra
COLT 2022

Clustering Mixtures with Almost Optimal Separation in Polynomial Time
Allen Liu, Jerry Li
STOC 2022, SIAM Journal on Computing Special Issue

Variable Decomposition for Prophet Inequalities and Optimal Ordering
Allen Liu, Renato Paes Leme, Martin Pal, Jon Schneider, Balasubramanian Sivan
EC 2021

Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu,Ankur Moitra
STOC 2021, Journal of the ACM 2023

Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over SO(3)
Allen Liu, Ankur Moitra
Manuscript

Optimal Contextual Pricing and Extensions
Allen Liu, Renato Paes Leme, Jon Schneider
SODA 2021

Distributed Load Balancing: A New Framework and Improved Guarantees
Sara Ahmadian, Allen Liu, Binghui Peng, Morteza Zadimoghaddam
ITCS 2021

Tensor Completion Made Practical
Allen Liu,Ankur Moitra
NeurIPS 2020

Myersonian Regression
Allen Liu, Renato Paes Leme, Jon Schneider
NeurIPS 2020

Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation
Allen Liu,Ankur Moitra
COLT 2020

Fourier and Circulant Matrices are Not Rigid
Zeev Dvir, Allen Liu
Preliminary version appeared in CCC 2019
Full version in Theory of Computing 2020

Efficiently Learning Mixtures of Mallows Models
Allen Liu, Ankur Moitra
FOCS 2018

Wavelet Decomposition and Bandwidth of Functions Defined on Vector Spaces over Finite Fields
Alex Iosevich, Allen Liu,Azita Mayeli, Jonathan Pakianathan
Bulletin of the Hellenic Mathematical Society 2018