Hi! My name is Stefan Tiegel, I am a PostDoc in the MIT Theory Group, hosted by Sam Hopkins, Guy Bresler, and Vinod Vaikuntanathan. My research is supported by an SNSF Postdoc.Mobility fellowship.

I'm broadly interested in the computational complexity of average-case problems with a focus on high-dimensional estimation and learning theory.

Previously, I was a doctoral student at ETH Zurich supervised by David Steurer.

E-Mail: stefan (dot) tiegel (at) inf (dot) ethz (dot) ch

Papers

• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point,
  with Hongjie Chen, Jingqiu Ding, Yiding Hua
  NeurIPS 2025, arxiv
  
• Sample-Optimal Private Regression in Polynomial Time,
  with Prashanti Anderson, Ainesh Bakshi, Mahbod Majid
  STOC 2025, arxiv
  
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More,
  with Ilias Diakonikolas, Samuel Hopkins, Ankit Pensia
  STOC 2025, arxiv
  
• Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations,
  with Kiril Bangachev, Guy Bresler, Vinod Vaikuntanathan
  STOC 2025, arxiv
  
• SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications,
  with Ilias Diakonikolas, Samuel Hopkins, Ankit Pensia
  STOC 2025, arxiv
  Invited to SICOMP Special Issue for STOC 2025
• Testably Learning Polynomial Threshold Functions,
  with Lucas Slot, Manuel Wiedmer
  NeurIPS 2024, arxiv
  
• Robust Mixture Learning when Outliers Overwhelm Small Groups,
  with Daniil Dmitriev, Rares Buhai, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang
  NeurIPS 2024, arxiv (author ordering by contribution)
  
• Improved Hardness Results for Learning Intersections of Halfspaces,
  COLT 2024, arxiv
  Best Student Paper Award
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression,
  with Rares Buhai, Jingqiu Ding,
  COLT 2024, arxiv
• Private estimation algorithms for stochastic block models and mixture models,
  with Hongjie Chen, Vincent Cohen-Addad, Tommaso d’Orsi, Alessandro Epasto, Jacob Imola, David Steurer,
  NeurIPS 2023 (spotlight), arxiv
• Robust Mean Estimation Without Moments for Symmetric Distributions,
  with Gleb Novikov, David Steurer,
  NeurIPS 2023, arxiv
• Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems,
  COLT 2023, arxiv
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise,
  with Rajai Nasser,
  COLT 2022, arxiv
• Fast algorithm for overcomplete order-3 tensor decomposition,
  with Jingqiu Ding, Tommaso d’Orsi, Chih-Hung Liu, David Steurer,
  COLT 2022, arxiv
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers,
  with Tommaso d’Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer,
  NeurIPS 2021, arxiv
• SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation,
  with David Steurer,
  SODA 2021, arxiv
  Recipient of the ETH medal for outstanding master theses
• A Framework for Searching in Graphs in the Presence of Errors,
  with Dariusz Dereniowski, Daniel Wolleb, Przemysław Uznański,
  SOSA 2019, arxiv