1 citations · 5 across the 13 of their papers we have counts for
6 papers · 1 filter
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 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 …
Robust Mean Estimation Without Moments for Symmetric Distributions
Gleb Novikov, David Steurer, Stefan Tiegel
We study the problem of robustly estimating the mean or location parameter without moment assumptions. We show that for a large class of symmetric distributions, the same error as…
Private estimation algorithms for stochastic block models and mixture models
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi +4
We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best know…
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
David Steurer, Stefan Tiegel
We develop a general framework to significantly reduce the degree of sum-of-squares proofs by introducing new variables. To illustrate the power of this framework, we use it to spe…
A Framework for Searching in Graphs in the Presence of Errors
Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański +1
We consider the problem of searching for an unknown target vertex in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex and the response either a…