I am an Assistant Professor of Computer Science at Harvard's John A. Paulson School of Engineering and Applied Sciences, where I am a member of the Theory of Computation group, the ML Foundations group, and the Harvard Quantum Initiative.
I work on designing algorithms with provable guarantees for fundamental problems in data science, especially in the context of generative modeling, deep learning, and quantum information.
Previously I was an NSF postdoc at UC Berkeley under the wise guidance of Prasad Raghavendra. I received my PhD in EECS from MIT as a member of CSAIL and the Theory of Computation group. I was very fortunate to be advised by Ankur Moitra and supported by an MIT Presidential Fellowship and a PD Soros Fellowship. Prior to MIT, I studied mathematics and computer science as an undergraduate at Harvard, where I had the pleasure and honor of working with Salil Vadhan and Leslie Valiant.
Email: sitan (at) seas (dot) harvard (dot) edu
Group:
Teaching:
Selected Papers (Show all):
 Faster DiffusionBased Sampling with Randomized Midpoints: Sequential and Parallel [pdf]
Shivam Gupta, Linda Cai, Sitan Chen
Manuscript
 Learning General Gaussian Mixtures with Efficient Score Matching [pdf]
Sitan Chen, Vasilis Kontonis, Kulin Shah
Manuscript
 Provably Learning a MultiHead Attention Layer [pdf], [slides]
Sitan Chen, Yuanzhi Li
Manuscript
 Efficient Pauli Channel Estimation with Logarithmic Quantum Memory [pdf]
Sitan Chen, Weiyuan Gong
Manuscript
 Optimal Tradeoffs for Estimating Pauli Observables [pdf]
Sitan Chen, Weiyuan Gong, Qi Ye
FOCS 2024
 A Faster and Simpler Algorithm for Learning Shallow Networks [pdf]
Sitan Chen, Shyam Narayanan
COLT 2024
 Critical Windows: NonAsymptotic Theory for Feature Emergence in Diffusion Models [pdf]
Marvin Li, Sitan Chen
ICML 2024
 An Optimal Tradeoff Between Entanglement and Copy Complexity for State Tomography [pdf]
Sitan Chen, Jerry Li, Allen Liu
STOC 2024
 Learning Mixtures of Gaussians Using the DDPM Objective [pdf]
Kulin Shah, Sitan Chen, Adam R. Klivans
NeurIPS 2023
 The Probability Flow ODE Is Provably Fast [pdf]
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, Adil Salim
NeurIPS 2023
 When Does Adaptivity Help for Quantum State Learning? [pdf] [slides] [video]
Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke
FOCS 2023
(Previously Tight Bounds for State Tomography with Incoherent Measurements, QIP 2023, merged with [CHLL22])
 Learning Narrow OneHiddenLayer ReLU Networks [pdf]
Sitan Chen, Zehao Dou, Surbhi Goel, Adam R. Klivans, Raghu Meka
COLT 2023
 RestorationDegradation Beyond Linear Diffusions: A NonAsymptotic Analysis For DDIMType Samplers [pdf]
Sitan Chen, Giannis Daras, Alexandros G. Dimakis
ICML 2023
 Learning Polynomial Transformations [pdf] [video]
Sitan Chen, Jerry Li, Yuanzhi Li, Anru R. Zhang
STOC 2023
 Sampling Is as Easy as Learning the Score: Theory for Diffusion Models With Minimal Data Assumptions [pdf] [slides]
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, Anru R. Zhang
ICLR 2023
Oral presentation
 Learning to Predict Arbitrary Quantum Processes [pdf] [slides] [journal]
HsinYuan Huang, Sitan Chen, John Preskill
QIP 2023, PRX Quantum
 The Complexity of NISQ [pdf] [slides] [video] [journal]
Sitan Chen, Jordan Cotler, HsinYuan Huang, Jerry Li
QIP 2023, Nature Communications
 Learning (Very) Simple Generative Models Is Hard [pdf]
Sitan Chen, Jerry Li, Yuanzhi Li
NeurIPS 2022
Oral presentation
 Hardness of NoiseFree Learning for TwoHiddenLayer Neural Networks [pdf]
Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka
NeurIPS 2022
Oral presentation
 Tight Bounds for Quantum State Certification with Incoherent Measurements [pdf] [slides] [video]
Sitan Chen, Brice Huang, Jerry Li, Allen Liu
FOCS 2022, QIP 2023
 Quantum Advantage in Learning From Experiments [pdf] [journal]
HsinYuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, Jarrod R. McClean
Science
 Kalman Filtering with Adversarial Corruptions [pdf]
Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
STOC 2022
 Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs [pdf]
Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
ICLR 2022
 A Hierarchy for Replica Quantum Advantage [pdf]
Sitan Chen, Jordan Cotler, HsinYuan Huang, Jerry Li
QIP 2022, merged with [CCHL21]
 Towards InstanceOptimal Quantum State Certification With Independent Measurements [pdf]
Sitan Chen, Jerry Li, Ryan O'Donnell
QIP 2022, COLT 2022
Blurb on Property Testing Review
 Symmetric Sparse Boolean Matrix Factorization and Applications [pdf]
Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
ITCS 2022
 Efficiently Learning One Hidden Layer ReLU Networks From Queries [pdf]
Sitan Chen, Adam R. Klivans, Raghu Meka
NeurIPS 2021
 Exponential Separations Between Learning With and Without Quantum Memory [pdf]
Sitan Chen, Jordan Cotler, HsinYuan Huang, Jerry Li
FOCS 2021, QIP 2022
Invited to SIAM Journal of Computing Special Issue
 Online and DistributionFree Robustness: Regression and Contextual Bandits with Huber Contamination [pdf]
Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
FOCS 2021
 Learning Deep ReLU Networks Is FixedParameter Tractable [pdf] [video]
Sitan Chen, Adam R. Klivans, Raghu Meka
FOCS 2021
 Algorithmic Foundations for the Diffraction Limit [pdf] [slides] [code] [video] [Ankur's Simons tutorial]
Sitan Chen, Ankur Moitra
STOC 2021
 On InstaHide, Phase Retrieval, and Sparse Matrix Factorization [pdf]
Sitan Chen, Xiaoxiao Li, Zhao Song, Danyang Zhuo
ICLR 2021
 Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [pdf] [code] [Ankur's Simons tutorial]
Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
NeurIPS 2020
Spotlight presentation
 Learning Structured Distributions from Untrusted Batches: Faster and Simpler [pdf] [code]
Sitan Chen, Jerry Li, Ankur Moitra
NeurIPS 2020
 Learning Polynomials of Few Relevant Dimensions [pdf] [slides] [video]
Sitan Chen, Raghu Meka
COLT 2020
 Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments [pdf] [slides] [video]
Sitan Chen, Jerry Li, Zhao Song
STOC 2020
 Efficiently Learning Structured Distributions from Untrusted Batches [pdf] [slides] [video]
Sitan Chen, Jerry Li, Ankur Moitra
STOC 2020
 Improved Bounds for Sampling Colorings via Linear Programming [pdf] [slides]
Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle
(merger of [CM18] and [DPP18])
SODA 2019
 Beyond the LowDegree Algorithm: Mixtures of Subcubes and Their Applications [pdf] [slides]
Sitan Chen, Ankur Moitra
STOC 2019
 Basis Collapse For Holographic Algorithms over All Domain Sizes [pdf] [slides] [video]
Sitan Chen
STOC 2016.
 Pseudorandomness for ReadOnce, ConstantDepth Circuits [pdf]
Sitan Chen, Thomas Steinke, Salil Vadhan
Manuscript
Thesis:
 Rethinking Algorithm Design for Modern Challenges in Data Science [pdf]
PhD Thesis, MIT, 2021
Service:
 PC Member: STOC 2024, SODA 2024, RANDOM 2023, ICALP 2022, FOCS 2022
Other:

