6 papers · 1 filter
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1
We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polyn…
Finding Colorings in One-Sided Expanders
Rares-Darius Buhai, Yiding Hua, David Steurer +1
We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example,…
Faster MAX-CUT on Bounded Threshold Rank Graphs
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman +1
We design new algorithms for approximating 2CSPs on graphs with bounded threshold rank, that is, whose normalized adjacency matrix has few eigenvalues larger than , sm…
Hesse's Redemption: Efficient Convex Polynomial Programming
Lucas Slot, David Steurer, Manuel Wiedmer
Efficient algorithms for convex optimization, such as the ellipsoid method, require an a priori bound on the radius of a ball around the origin guaranteed to contain an optimal sol…
Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
Hongjie Chen, Deepak Narayanan Sridharan, David Steurer
We revisit the problem of estimating the mean of a high-dimensional distribution in the presence of an -fraction of adversarial outliers. When is at most…
Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Hongjie Chen, Jingqiu Ding, Yiding Hua +1
We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of ErdÅs-Rényi random graphs and their generalization, inhomo…