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.

Much of my work centers around algorithms based on the sum-of-squares hierarchy of semidefinite programs and deriving reduction-based hardness results. I'm also excited about applications of semidefinite programming to other areas.

Previously, I was a doctoral student at ETH Zurich supervised by David Steurer. A copy of my doctoral thesis can be found here.

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

Papers

Below are some selected/recent papers of mine. For a list sorted by topic, click here. For a chronological list click here.

Recent and Selected Papers

• Rigorous Implications of the Low-Degree Heuristic,
  with Jun-Ting Hsieh, Daniel Kane, Pravesh Kothari, Jerry Li, Sidhanth Mohanty
  STOC 2026, 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
• Improved Hardness Results for Learning Intersections of Halfspaces,
  COLT 2024, arxiv
  Best Student Paper Award
• Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems,
  COLT 2023, arxiv