Current Group

• Weiyuan Gong (PhD, 2023-) Von Neumann Fellowship
• Aayush Karan (PhD, 2023-, co-advised with Yilun Du) PD Soros Fellow NDSEG Kempner Fellow
• Jaeyeon Kim (PhD, 2024-, co-advised with Sham Kakade)
• Walt McKelvie (PhD, 2024-, co-advised with Salil Vadhan) NSF GRFP
• Kevin Cong (undergrad, 2025-)

Former Group Members

• Yunchao Liu (postdoc, 2024-2025, → IBM Quantum, co-advised with Anurag Anshu)
• Marvin Li (undergrad, 2023-2025, → Hudson River Trading) Hoopes Prize Fay Prize
• Arif Kerem Dayi (undergrad, 2024-2025, → MIT EECS PhD) Hoopes Prize CRA Finalist
• Zhihan Zhang (undergrad, 2024-2025, → Caltech CS PhD)

Teaching

• CS 2233: Quantum Learning Theory (Fall 25)
• CS 1240: Algorithms and Data Structures (Spring 25)
• CS 2243: Algorithms for Data Science (Fall 24)
• CS 124: Algorithms and Data Structures (Spring 24)
• CS 224: Algorithms for Data Science (Fall 23)

Recent Papers

• A Provably Efficient Method for Tensor Ring Decomposition and Its Applications [pdf]
  Han Chen, Sitan Chen, Anru R. Zhang
  Manuscript
• Sublinear Iterations Can Suffice Even for DDPMs [pdf]
  Matthew S. Zhang, Stephen Huan, Jerry Huang, Nicholas M. Boffi, Sitan Chen, Sinho Chewi
  Manuscript
• Optimal Inference Schedules for Masked Diffusion Models [pdf]
  Sitan Chen, Kevin Cong, Jerry Li
  Manuscript
• Quantum Probe Tomography [pdf]
  Sitan Chen, Jordan Cotler, Hsin-Yuan Huang
  Manuscript
• Fine-Tuning Masked Diffusion for Provable Self-Correction [pdf]
  Jaeyeon Kim, Seunggeun Kim, Taekyun Lee, David Z. Pan, Hyeji Kim, Sham Kakade, Sitan Chen
  Manuscript
• Selective Underfitting in Diffusion Models [pdf] [website]
  Kiwhan Song, Jaeyeon Kim, Sitan Chen, Yilun Du, Sham Kakade, Vincent Sitzmann
  Manuscript
• Any-Order Flexible Length Masked Diffusion [pdf] [website] [code]
  Jaeyeon Kim, Lee Cheuk-Kit, Carles Domingo-Enrich, Yilun Du, Sham Kakade, Timothy Ngotiaoco, Sitan Chen, Michael Albergo
  Manuscript
• ReGuidance: A Simple Diffusion Wrapper for Boosting Sample Quality on Hard Inverse Problems [pdf]
  Aayush Karan, Kulin Shah, Sitan Chen
  Manuscript

1. A Provably Efficient Method for Tensor Ring Decomposition and Its Applications [pdf]
   Han Chen, Sitan Chen, Anru R. Zhang
   Manuscript
2. Sublinear Iterations Can Suffice Even for DDPMs [pdf]
   Matthew S. Zhang, Stephen Huan, Jerry Huang, Nicholas M. Boffi, Sitan Chen, Sinho Chewi
   Manuscript
3. Optimal Inference Schedules for Masked Diffusion Models [pdf]
   Sitan Chen, Kevin Cong, Jerry Li
   Manuscript
4. Quantum Probe Tomography [pdf]
   Sitan Chen, Jordan Cotler, Hsin-Yuan Huang
   Manuscript
5. Fine-Tuning Masked Diffusion for Provable Self-Correction [pdf]
   Jaeyeon Kim, Seunggeun Kim, Taekyun Lee, David Z. Pan, Hyeji Kim, Sham Kakade, Sitan Chen
   Manuscript
6. Selective Underfitting in Diffusion Models [pdf] [website]
   Kiwhan Song, Jaeyeon Kim, Sitan Chen, Yilun Du, Sham Kakade, Vincent Sitzmann
   Manuscript
7. Any-Order Flexible Length Masked Diffusion [pdf] [website] [code]
   Jaeyeon Kim, Lee Cheuk-Kit, Carles Domingo-Enrich, Yilun Du, Sham Kakade, Timothy Ngotiaoco, Sitan Chen, Michael Albergo
   Manuscript
8. ReGuidance: A Simple Diffusion Wrapper for Boosting Sample Quality on Hard Inverse Problems [pdf]
   Aayush Karan, Kulin Shah, Sitan Chen
   Manuscript
9. Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood [pdf]
   Sitan Chen, Weiyuan Gong, Jonas Haferkamp, Yihui Quek
   QIP 2026
10. S4S: Solving for a Diffusion Model Solver [pdf]
    Eric Frankel, Sitan Chen, Jerry Li, Pang Wei Koh, Lillian J. Ratliff, Sewoong Oh
    ICML 2025
11. Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions [pdf]
    Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham Kakade, Sitan Chen
    ICML 2025
    Outstanding Paper Award
12. Blink of an Eye: A Simple Theory for Feature Localization in Generative Models [pdf]
    Marvin Li, Aayush Karan, Sitan Chen
    ICML 2025
    Oral presentation
13. Gradient Dynamics for Low-Rank Fine-Tuning Beyond Kernels [pdf] [slides]
    Arif Kerem Dayi, Sitan Chen
    COLT 2025
14. Predicting Quantum Channels Over General Product Distributions [pdf]
    Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Li
    COLT 2025
15. Learning General Gaussian Mixtures with Efficient Score Matching [pdf]
    Sitan Chen, Vasilis Kontonis, Kulin Shah
    COLT 2025
16. Provably Learning a Multi-Head Attention Layer [pdf] [slides]
    Sitan Chen, Yuanzhi Li
    STOC 2025
17. Stabilizer Bootstrapping: A Recipe for Agnostic Tomography and Magic Estimation [pdf]
    Sitan Chen, Weiyuan Gong, Qi Ye, Zhihan Zhang
    STOC 2025, QIP 2025
    Short plenary talk
18. Faster Diffusion-Based Sampling with Randomized Midpoints: Sequential and Parallel [pdf]
    Shivam Gupta, Linda Cai, Sitan Chen
    ICLR 2025
19. Optimal High-Precision Shadow Estimation [pdf]
    Sitan Chen, Jerry Li, Allen Liu
    QIP 2025, merged with [CLL24a]
20. Efficient Pauli Channel Estimation with Logarithmic Quantum Memory [pdf] [journal]
    Sitan Chen, Weiyuan Gong
    QIP 2025, PRX Quantum
21. 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
22. Unrolled Denoising Networks Provably Learn Optimal Bayesian Inference [pdf]
    Aayush Karan, Kulin Shah, Sitan Chen, Yonina C. Eldar
    NeurIPS 2024
23. Optimal Tradeoffs for Estimating Pauli Observables [pdf]
    Sitan Chen, Weiyuan Gong, Qi Ye
    FOCS 2024, QIP 2025
    Quanta Magazine, Wired Magazine
24. A Faster and Simpler Algorithm for Learning Shallow Networks [pdf]
    Sitan Chen, Shyam Narayanan
    COLT 2024
25. Critical Windows: Non-Asymptotic Theory for Feature Emergence in Diffusion Models [pdf]
    Marvin Li, Sitan Chen
    ICML 2024
26. An Optimal Tradeoff Between Entanglement and Copy Complexity for State Tomography [pdf]
    Sitan Chen, Jerry Li, Allen Liu
    STOC 2024, QIP 2025
27. Learning Mixtures of Gaussians Using the DDPM Objective [pdf]
    Kulin Shah, Sitan Chen, Adam R. Klivans
    NeurIPS 2023
28. The Probability Flow ODE Is Provably Fast [pdf]
    Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, Adil Salim
    NeurIPS 2023
29. When Does Adaptivity Help for Quantum State Learning? [pdf] [slides] [video]
    Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke
    FOCS 2023, QIP 2023
30. Learning Narrow One-Hidden-Layer ReLU Networks [pdf]
    Sitan Chen, Zehao Dou, Surbhi Goel, Adam R. Klivans, Raghu Meka
    COLT 2023
31. Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [pdf]
    Sitan Chen, Giannis Daras, Alexandros G. Dimakis
    ICML 2023
32. Learning Polynomial Transformations [pdf] [video]
    Sitan Chen, Jerry Li, Yuanzhi Li, Anru R. Zhang
    STOC 2023
33. 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
34. Learning to Predict Arbitrary Quantum Processes [pdf] [slides] [journal]
    Hsin-Yuan Huang, Sitan Chen, John Preskill
    QIP 2023, PRX Quantum
35. The Complexity of NISQ [pdf] [slides] [video] [journal]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    QIP 2023, Nature Communications
36. Learning (Very) Simple Generative Models Is Hard [pdf]
    Sitan Chen, Jerry Li, Yuanzhi Li
    NeurIPS 2022
    Oral presentation
37. 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
38. Tight Bounds for Quantum State Certification with Incoherent Measurements [pdf] [slides] [video]
    Sitan Chen, Brice Huang, Jerry Li, Allen Liu
    FOCS 2022, QIP 2023
39. 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
40. Kalman Filtering with Adversarial Corruptions [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    STOC 2022
41. Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs [pdf]
    Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
    ICLR 2022
42. A Hierarchy for Replica Quantum Advantage [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    QIP 2022, merged with [CCHL21]
43. 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
44. Symmetric Sparse Boolean Matrix Factorization and Applications [pdf]
    Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
    ITCS 2022
45. Efficiently Learning One Hidden Layer ReLU Networks From Queries [pdf]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    NeurIPS 2021
46. 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
47. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    FOCS 2021
48. Learning Deep ReLU Networks Is Fixed-Parameter Tractable [pdf] [video]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    FOCS 2021
49. Algorithmic Foundations for the Diffraction Limit [pdf] [slides] [code] [video] [Ankur's Simons tutorial]
    Sitan Chen, Ankur Moitra
    STOC 2021
50. On InstaHide, Phase Retrieval, and Sparse Matrix Factorization [pdf]
    Sitan Chen, Xiaoxiao Li, Zhao Song, Danyang Zhuo
    ICLR 2021
51. 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 paper
52. Learning Structured Distributions from Untrusted Batches: Faster and Simpler [pdf] [code]
    Sitan Chen, Jerry Li, Ankur Moitra
    NeurIPS 2020
53. Entanglement is Necessary for Optimal Quantum Property Testing [pdf] [slides] [video]
    Sebastien Bubeck, Sitan Chen, Jerry Li
    FOCS 2020
    Blurb on Property Testing Review
54. Learning Polynomials of Few Relevant Dimensions [pdf] [slides] [video]
    Sitan Chen, Raghu Meka
    COLT 2020
55. Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Zhao Song
    STOC 2020
56. Efficiently Learning Structured Distributions from Untrusted Batches [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Ankur Moitra
    STOC 2020
57. 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
58. Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications [pdf] [slides]
    Sitan Chen, Ankur Moitra
    STOC 2019
59. Basis Collapse For Holographic Algorithms over All Domain Sizes [pdf] [slides] [video]
    Sitan Chen
    STOC 2016
60. 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: QIP 2026, FOCS 2025, STOC 2024, SODA 2024, RANDOM 2023, ICALP 2022, FOCS 2022

Other

• A note showing an exponential separation between adaptive and non-adaptive quantum learning protocols (joint with Weiyuan Gong and Zhihan Zhang)
• Workshop on quantum learning at FOCS 2024
• A general-audience exposition I wrote for Nature Physics News & Views (2024) on [Haah-Kothari-Tang]
• Reading group on cryptographic lower bounds for learning at Simons Institute, Fall '21
• Some piano performances I've given: 2021, 2019a, 2019b, 2018, 2017