Hi! My name is Stefan Tiegel, I am a fifth-year PhD student in theoretical computer science at ETH Zurich, supervised by David Steurer. I'm broadly interested in the computational complexity of average-case problems with a focus on high-dimensional estimation and learning theory.

I had the pleasure of visiting Sam Hopkins at MIT for the academic year 2023/24.

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

Papers

• Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations,
  with Kiril Bangachev, Guy Bresler, Vinod Vaikuntanathan
  Manuscript, arxiv
  
• SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications,
  with Ilias Diakonikolas, Samuel Hopkins, Ankit Pensia
  Manuscript, arxiv
  
• 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