11 citations · 14 across the 3 of their papers we have counts for
3 papers
cs.LG2020★ 11 cited
Differentially Private Clustering: Tight Approximation Ratios
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient…
cs.LG2020★ 3 cited
Near-tight closure bounds for Littlestone and threshold dimensions
Badih Ghazi, Noah Golowich, Ravi Kumar +1
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes of Boolean functions wit…
cs.IT2016
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE…