Hi! My name is Stefan Tiegel, I am a fourth-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 am visiting Sam Hopkins at MIT for the academic year 2023/24.

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

Papers

• Improved Hardness Results for Learning Intersections of Halfspaces
  Preprint, arxiv
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression,
  with Rares Buhai, Jingqiu Ding,
  Preprint, 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