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
Current Group:
 Yunchao Liu (postdoc, 2023, coadvised with Anurag Anshu)
 Weiyuan Gong (PhD, 2023)
 Aayush Karan (PhD, 2023, coadvised with H.T. Kung)
 Jaeyeon Kim (PhD, 2024, coadvised with Sham Kakade)
 Walt McKelvie (PhD, 2024, coadvised with Salil Vadhan)
 Marvin Li (undergrad, 2023)
 Arif Kerem Dayi (undergrad, 2024)
 Zhihan Zhang (undergrad, 2024)
Teaching:
Selected Papers (Show all):
 Predicting Quantum Channels Over General Product Distributions [pdf]
Sitan Chen, Jaume de Dios Pont, JunTing Hsieh, HsinYuan Huang, Jane Lange, Jerry Li
Manuscript
 Stabilizer Bootstrapping: A Recipe for Agnostic Tomography and Magic Estimation [pdf]
Sitan Chen, Weiyuan Gong, Qi Ye, Zhihan Zhang
Manuscript
 Optimal HighPrecision Shadow Estimation [pdf]
Sitan Chen, Jerry Li, Allen Liu
Manuscript
 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
 What Does Guidance Do? A FineGrained Analysis in a Simple Setting [pdf]
Muthu Chidambaram, Khashayar Gatmiry, Sitan Chen, Holden Lee, Jianfeng Lu
NeurIPS 2024
 Unrolled Denoising Networks Provably Learn Optimal Bayesian Inference [pdf]
Aayush Karan, Kulin Shah, Sitan Chen, Yonina C. Eldar
NeurIPS 2024
 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:

