Allen Liu

I am currently a fourth-year graduate student in EECS at MIT working under the wonderful supervision of Ankur Moitra. I also completed my undergraduate degree (in mathematics) at MIT. I am generally interested in algorithms and learning theory, particularly developing algorithms for machine learning with provable guarantees. I am also interested in applying tools from learning theory to understand problems in quantum information. My work is supported by an NSF Graduate Research Fellowship and a Hertz Fellowship.

Email: cliu568 at mit dot edu

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

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

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

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

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

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

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

Learning Mixtures of Linear Dynamical Systems
with Ainesh Bakshi, Ankur Moitra, Morris Yau
ICML 2023

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

Robust Voting Rules from Algorithmic Robust Statistics
with Ankur Moitra
SODA 2023

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

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

Minimax Rates for Robust Community Detection
with Ankur Moitra
FOCS 2022

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

Learning GMMs with Nearly Optimal Robustness Guarantees
with Ankur Moitra
COLT 2022

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

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

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

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

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

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

Tensor Completion Made Practical
with Ankur Moitra
NeurIPS 2020

Myersonian Regression
with Renato Paes Leme, Jon Schneider
NeurIPS 2020

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

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

Efficiently Learning Mixtures of Mallows Models
with Ankur Moitra
FOCS 2018

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