1 citations · 1 across the 2 of their papers we have counts for
7 papers
Algorithms with Polynomially-Improved Approximation Factors for the Norm, and Applications
Samuel B. Hopkins, Stefan Tiegel
The norm of a matrix is defined as . We give…
Improved Hardness Results for Learning Intersections of Halfspaces
Stefan Tiegel
We show strong (and surprisingly simple) lower bounds for weakly learning intersections of halfspaces in the improper setting. Strikingly little is known about this problem. For in…
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
Improved Robust Estimation for ErdÅs-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Hongjie Chen, Jingqiu Ding, Yiding Hua +1
We study the problem of robustly estimating the edge density of ErdÅs-Rényi random graphs when an adversary can arbitrarily add or remove edges incident to an $…
Testably Learning Polynomial Threshold Functions
Lucas Slot, Stefan Tiegel, Manuel Wiedmer
Rubinfeld & Vasilyan recently introduced the framework of testable learning as an extension of the classical agnostic model. It relaxes distributional assumptions which are difficu…
Robust Mixture Learning when Outliers Overwhelm Small Groups
Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel +5
We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fractio…