Sitan Chen

I am an NSF postdoc at UC Berkeley hosted by Prasad Raghavendra, and a Research Fellow at the Simons Institute. I work on designing algorithms with provable guarantees for fundamental problems in data science, especially in the context of generative modeling, robustness, and deep learning. I also enjoy exploring what techniques for such problems can tell us about inverse problems in the sciences, most recently with regards to understanding the capabilities of near-term quantum devices.

Recently, 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.

Announcement: In Fall of 2023, I will join the Theory of Computation group at Harvard's John A. Paulson School of Engineering and Applied Sciences as an Assistant Professor of Computer Science.
I am looking for motivated graduate students to join my group. If you are interested in working with me, you should apply to the PhD program in computer science at Harvard by December 15.

Email: sitan (at) seas (dot) harvard (dot) edu
CV (last updated 9/10/21)

Papers (authors alphabetical unless not):

  1. Sampling Is as Easy as Learning the Score: Theory for Diffusion Models With Minimal Data Assumptions [pdf]
    Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, Anru R. Zhang
    In submission
  2. Learning Polynomial Transformations [pdf] [video]
    Sitan Chen, Jerry Li, Yuanzhi Li, Anru R. Zhang
    In submission
  3. Learning to Predict Arbitrary Quantum Processes [pdf]
    Hsin-Yuan Huang, Sitan Chen, John Preskill
    QIP 2023
  4. The Complexity of NISQ [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    QIP 2023
  5. Tight Bounds for State Tomography with Incoherent Measurements [pdf]
    Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke
    QIP 2023, merged with [CHLL22]
  6. Learning (Very) Simple Generative Models Is Hard [pdf]
    Sitan Chen, Jerry Li, Yuanzhi Li
    NeurIPS 2022
    Oral presentation
  7. 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
  8. Tight Bounds for Quantum State Certification with Incoherent Measurements [pdf]
    Sitan Chen, Brice Huang, Jerry Li, Allen Liu
    FOCS 2022, QIP 2023
  9. 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
  10. Kalman Filtering with Adversarial Corruptions [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    STOC 2022
  11. Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs [pdf]
    Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
    ICLR 2022
  12. A Hierarchy for Replica Quantum Advantage [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    QIP 2022, merged with [CCHL21]
  13. 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
  14. Symmetric Sparse Boolean Matrix Factorization and Applications [pdf]
    Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
    ITCS 2022
  15. Efficiently Learning One Hidden Layer ReLU Networks From Queries [pdf]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    NeurIPS 2021
  16. 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
  17. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    FOCS 2021
  18. Learning Deep ReLU Networks Is Fixed-Parameter Tractable [pdf] [video]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    FOCS 2021
  19. Algorithmic Foundations for the Diffraction Limit [pdf] [slides] [code] [video] [Ankur's Simons tutorial]
    Sitan Chen, Ankur Moitra
    STOC 2021
  20. On InstaHide, Phase Retrieval, and Sparse Matrix Factorization [pdf]
    Sitan Chen, Xiaoxiao Li, Zhao Song, Danyang Zhuo
    ICLR 2021
  21. 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
  22. Learning Structured Distributions from Untrusted Batches: Faster and Simpler [pdf] [code]
    Sitan Chen, Jerry Li, Ankur Moitra
    NeurIPS 2020
  23. Entanglement is Necessary for Optimal Quantum Property Testing [pdf] [slides] [video]
    Sebastien Bubeck, Sitan Chen, Jerry Li
    FOCS 2020
    Blurb on Property Testing Review
  24. Learning Polynomials of Few Relevant Dimensions [pdf] [slides] [video]
    Sitan Chen, Raghu Meka
    COLT 2020
  25. Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Zhao Song
    STOC 2020
  26. Efficiently Learning Structured Distributions from Untrusted Batches [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Ankur Moitra
    STOC 2020
  27. 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
  28. Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications [pdf] [slides]
    Sitan Chen, Ankur Moitra
    STOC 2019
  29. Basis Collapse For Holographic Algorithms over All Domain Sizes [pdf] [slides] [video]
    Sitan Chen
    STOC 2016.
  30. Pseudorandomness for Read-Once, Constant-Depth Circuits [pdf]
    Sitan Chen, Thomas Steinke, Salil Vadhan
    Manuscript

Theses:

  • Rethinking Algorithm Design for Modern Challenges in Data Science [pdf]
    PhD Thesis, 2021
  • Geometry in Algorithms and Complexity: Holographic Algorithms and Valiant's Conjecture [pdf]
    Undergraduate Thesis, 2016
    Thomas Hoopes Prize, Captain Jonathan Fay Prize (for best Harvard undergraduate theses), New World Mathematics Award

Service:

  • PC Member: FOCS 2022, ICALP 2022

Other:

 
picture of me