Sitan Chen

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


Announcement: I am co-organizing a workshop on quantum learning at FOCS 2024, see here for details!


Current Group:


Teaching:


Selected Papers (Show all):

  1. Predicting Quantum Channels Over General Product Distributions [pdf]
    Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Li
    Manuscript
  2. Stabilizer Bootstrapping: A Recipe for Agnostic Tomography and Magic Estimation [pdf]
    Sitan Chen, Weiyuan Gong, Qi Ye, Zhihan Zhang
    Manuscript
  3. Optimal High-Precision Shadow Estimation [pdf]
    Sitan Chen, Jerry Li, Allen Liu
    Manuscript
  4. Faster Diffusion-Based Sampling with Randomized Midpoints: Sequential and Parallel [pdf]
    Shivam Gupta, Linda Cai, Sitan Chen
    Manuscript
  5. Learning General Gaussian Mixtures with Efficient Score Matching [pdf]
    Sitan Chen, Vasilis Kontonis, Kulin Shah
    Manuscript
  6. Provably Learning a Multi-Head Attention Layer [pdf], [slides]
    Sitan Chen, Yuanzhi Li
    Manuscript
  7. Efficient Pauli Channel Estimation with Logarithmic Quantum Memory [pdf]
    Sitan Chen, Weiyuan Gong
    Manuscript
  8. What Does Guidance Do? A Fine-Grained Analysis in a Simple Setting [pdf]
    Muthu Chidambaram, Khashayar Gatmiry, Sitan Chen, Holden Lee, Jianfeng Lu
    NeurIPS 2024
  9. Unrolled Denoising Networks Provably Learn Optimal Bayesian Inference [pdf]
    Aayush Karan, Kulin Shah, Sitan Chen, Yonina C. Eldar
    NeurIPS 2024
  10. Optimal Tradeoffs for Estimating Pauli Observables [pdf]
    Sitan Chen, Weiyuan Gong, Qi Ye
    FOCS 2024
    Quanta Magazine
  11. A Faster and Simpler Algorithm for Learning Shallow Networks [pdf]
    Sitan Chen, Shyam Narayanan
    COLT 2024
  12. Critical Windows: Non-Asymptotic Theory for Feature Emergence in Diffusion Models [pdf]
    Marvin Li, Sitan Chen
    ICML 2024
  13. An Optimal Tradeoff Between Entanglement and Copy Complexity for State Tomography [pdf]
    Sitan Chen, Jerry Li, Allen Liu
    STOC 2024
  14. Learning Mixtures of Gaussians Using the DDPM Objective [pdf]
    Kulin Shah, Sitan Chen, Adam R. Klivans
    NeurIPS 2023
  15. The Probability Flow ODE Is Provably Fast [pdf]
    Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, Adil Salim
    NeurIPS 2023
  16. 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])
  17. Learning Narrow One-Hidden-Layer ReLU Networks [pdf]
    Sitan Chen, Zehao Dou, Surbhi Goel, Adam R. Klivans, Raghu Meka
    COLT 2023
  18. Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [pdf]
    Sitan Chen, Giannis Daras, Alexandros G. Dimakis
    ICML 2023
  19. Learning Polynomial Transformations [pdf] [video]
    Sitan Chen, Jerry Li, Yuanzhi Li, Anru R. Zhang
    STOC 2023
  20. 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
  21. Learning to Predict Arbitrary Quantum Processes [pdf] [slides] [journal]
    Hsin-Yuan Huang, Sitan Chen, John Preskill
    QIP 2023, PRX Quantum
  22. The Complexity of NISQ [pdf] [slides] [video] [journal]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    QIP 2023, Nature Communications
  23. Learning (Very) Simple Generative Models Is Hard [pdf]
    Sitan Chen, Jerry Li, Yuanzhi Li
    NeurIPS 2022
    Oral presentation
  24. Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks [pdf]
    Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka
    NeurIPS 2022
    Oral presentation
  25. Tight Bounds for Quantum State Certification with Incoherent Measurements [pdf] [slides] [video]
    Sitan Chen, Brice Huang, Jerry Li, Allen Liu
    FOCS 2022, QIP 2023
  26. Quantum Advantage in Learning From Experiments [pdf] [journal]
    Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, Jarrod R. McClean
    Science
  27. Kalman Filtering with Adversarial Corruptions [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    STOC 2022
  28. Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs [pdf]
    Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
    ICLR 2022
  29. A Hierarchy for Replica Quantum Advantage [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    QIP 2022, merged with [CCHL21]
  30. Towards Instance-Optimal Quantum State Certification With Independent Measurements [pdf]
    Sitan Chen, Jerry Li, Ryan O'Donnell
    QIP 2022, COLT 2022
    Blurb on Property Testing Review
  31. Symmetric Sparse Boolean Matrix Factorization and Applications [pdf]
    Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
    ITCS 2022
  32. Efficiently Learning One Hidden Layer ReLU Networks From Queries [pdf]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    NeurIPS 2021
  33. Exponential Separations Between Learning With and Without Quantum Memory [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    FOCS 2021, QIP 2022
    Invited to SIAM Journal of Computing Special Issue
  34. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    FOCS 2021
  35. Learning Deep ReLU Networks Is Fixed-Parameter Tractable [pdf] [video]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    FOCS 2021
  36. Algorithmic Foundations for the Diffraction Limit [pdf] [slides] [code] [video] [Ankur's Simons tutorial]
    Sitan Chen, Ankur Moitra
    STOC 2021
  37. On InstaHide, Phase Retrieval, and Sparse Matrix Factorization [pdf]
    Sitan Chen, Xiaoxiao Li, Zhao Song, Danyang Zhuo
    ICLR 2021
  38. 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
  39. Learning Structured Distributions from Untrusted Batches: Faster and Simpler [pdf] [code]
    Sitan Chen, Jerry Li, Ankur Moitra
    NeurIPS 2020
  40. Entanglement is Necessary for Optimal Quantum Property Testing [pdf] [slides] [video]
    Sebastien Bubeck, Sitan Chen, Jerry Li
    FOCS 2020
    Blurb on Property Testing Review
  41. Learning Polynomials of Few Relevant Dimensions [pdf] [slides] [video]
    Sitan Chen, Raghu Meka
    COLT 2020
  42. Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Zhao Song
    STOC 2020
  43. Efficiently Learning Structured Distributions from Untrusted Batches [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Ankur Moitra
    STOC 2020
  44. 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
  45. Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications [pdf] [slides]
    Sitan Chen, Ankur Moitra
    STOC 2019
  46. Basis Collapse For Holographic Algorithms over All Domain Sizes [pdf] [slides] [video]
    Sitan Chen
    STOC 2016.
  47. Pseudorandomness for Read-Once, Constant-Depth 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:

 
picture of me