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.

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

• 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