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 settings where data might be heterogeneous or contaminated. I also enjoy exploring what techniques for such problems can tell us about inverse problems in the sciences, e.g. in the context of quantum information.

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.

Email: sitan (at) seas (dot) harvard (dot) edu
CV (last updated 1/26/21)

Papers (authors alphabetical):

  1. Kalman Filtering with Adversarial Corruptions [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
  2. A Hierarchy for Replica Quantum Advantage [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
  3. Towards Instance-Optimal Quantum State Certification With Independent Measurements [pdf]
    Sitan Chen, Jerry Li, Ryan O'Donnell
    Blurb on Property Testing Review
  4. Symmetric Sparse Boolean Matrix Factorization and Applications [pdf]
    Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
    ITCS 2022
  5. Efficiently Learning One Hidden Layer ReLU Networks From Queries [pdf]
    Sitan Chen, Adam Klivans, Raghu Meka
    NeurIPS 2021
  6. Exponential Separations Between Learning With and Without Quantum Memory [pdf]
    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
    FOCS 2021
    Invited to SIAM Journal of Computing Special Issue
  7. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [pdf]
    Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
    FOCS 2021
  8. Learning Deep ReLU Networks Is Fixed-Parameter Tractable [pdf] [video]
    Sitan Chen, Adam R. Klivans, Raghu Meka
    FOCS 2021
  9. Algorithmic Foundations for the Diffraction Limit [pdf] [slides] [code] [video] [Ankur's Simons tutorial]
    Sitan Chen, Ankur Moitra
    STOC 2021
  10. On InstaHide, Phase Retrieval, and Sparse Matrix Factorization [pdf]
    Sitan Chen, Xiaoxiao Li, Zhao Song, Danyang Zhuo
    ICLR 2021
  11. 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
  12. Learning Structured Distributions from Untrusted Batches: Faster and Simpler [pdf] [code]
    Sitan Chen, Jerry Li, Ankur Moitra
    NeurIPS 2020
  13. Entanglement is Necessary for Optimal Quantum Property Testing [pdf] [slides] [video]
    Sebastien Bubeck, Sitan Chen, Jerry Li
    FOCS 2020
    Blurb on Property Testing Review
  14. Learning Polynomials of Few Relevant Dimensions [pdf] [slides] [video]
    Sitan Chen, Raghu Meka
    COLT 2020
  15. Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Zhao Song
    STOC 2020
  16. Efficiently Learning Structured Distributions from Untrusted Batches [pdf] [slides] [video]
    Sitan Chen, Jerry Li, Ankur Moitra
    STOC 2020
  17. 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
  18. Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications [pdf] [slides]
    Sitan Chen, Ankur Moitra
    STOC 2019
  19. Basis Collapse For Holographic Algorithms over All Domain Sizes [pdf] [slides] [video]
    Sitan Chen
    STOC 2016.
  20. Pseudorandomness for Read-Once, Constant-Depth Circuits [pdf]
    Sitan Chen, Thomas Steinke, Salil Vadhan


  • 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


  • PC Member: ICALP 2022


picture of me