Sitan Chen

I am a final-year graduate student in the EECS department at MIT and a member of CSAIL and the Theory of Computation group. I am very fortunate to be advised by Ankur Moitra and have been generously 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.

Research Interests: I work on algorithmic aspects of machine learning, with an emphasis on getting provable guarantees for fundamental learning problems arising in algorithmic robust statistics, deep learning, mixture models, quantum information, and inverse problems in the sciences. I also enjoy thinking about counting complexity.

Announcement: In the 2023-2024 academic year, 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. In the interim, I will be an NSF postdoc at UC Berkeley.

Email: sitanc (at) mit (dot) edu
CV (last updated 1/26/21)


  1. Towards Instance-Optimal Quantum State Certification With Independent Measurements [pdf]
    with Jerry Li and Ryan O'Donnell
    Blurb on Property Testing Review
  2. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [pdf]
    with Frederic Koehler, Ankur Moitra, and Morris Yau
  3. Learning Deep ReLU Networks Is Fixed-Parameter Tractable [pdf] [video]
    with Adam R. Klivans and Raghu Meka
  4. Symmetric Boolean Factor Analysis with Applications to InstaHide [pdf]
    with Zhao Song, Runzhou Tao, and Ruizhe Zhang
    In submission
  5. Algorithmic Foundations for the Diffraction Limit [pdf] [slides] [code] [video] [Ankur's Simons tutorial]
    with Ankur Moitra
    STOC 2021
  6. On InstaHide, Phase Retrieval, and Sparse Matrix Factorization [pdf]
    with Xiaoxiao Li, Zhao Song, and Danyang Zhuo
    ICLR 2021
  7. Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [pdf] [code] [Ankur's Simons tutorial]
    with Frederic Koehler, Ankur Moitra, and Morris Yau
    NeurIPS 2020 (spotlight)
  8. Learning Structured Distributions from Untrusted Batches: Faster and Simpler [pdf] [code]
    with Jerry Li and Ankur Moitra
    NeurIPS 2020
  9. Entanglement is Necessary for Optimal Quantum Property Testing [pdf] [slides] [video]
    with Sebastien Bubeck and Jerry Li
    FOCS 2020
    Blurb on Property Testing Review
  10. Learning Polynomials of Few Relevant Dimensions [pdf] [slides] [video]
    with Raghu Meka
    COLT 2020
  11. Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments [pdf] [slides] [video]
    with Jerry Li and Zhao Song
    STOC 2020
  12. Efficiently Learning Structured Distributions from Untrusted Batches [pdf] [slides] [video]
    with Jerry Li and Ankur Moitra
    STOC 2020
  13. Improved Bounds for Sampling Colorings via Linear Programming [pdf] [slides]
    with Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle
    (merger of [CM18] and [DPP18])
    SODA 2019
  14. Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications [pdf] [slides]
    with Ankur Moitra
    STOC 2019
  15. Basis Collapse For Holographic Algorithms over All Domain Sizes [pdf] [slides] [video]
    STOC 2016.
  16. Geometry in Algorithms and Complexity: Holographic Algorithms and Valiant's Conjecture [pdf]
    Senior thesis, Thomas Hoopes Prize, Captain Jonathan Fay Prize (for best Harvard undergraduate theses), New World Mathematics Award
  17. Pseudorandomness for Read-Once, Constant-Depth Circuits [pdf]
    with Thomas Steinke and Salil Vadhan


picture of me