46 citations · 304 across the 59 of their papers we have counts for
7 papers · 1 filter
Adversarially Robust Low Dimensional Representations
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen +1
Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical…
Bilu-Linial stability, certified algorithms and the Independent Set problem
Haris Angelidakis, Pranjal Awasthi, Avrim Blum +2
We study the Maximum Independent Set (MIS) problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of MIS is -stable if it has a unique o…
Clustering Semi-Random Mixtures of Gaussians
Pranjal Awasthi, Aravindan Vijayaraghavan
Gaussian mixture models (GMM) are the most widely used statistical model for the -means clustering problem and form a popular framework for clustering in machine learning and da…
Robust Communication-Optimal Distributed Clustering Algorithms
Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan +2
In this work, we study the -median and -means clustering problems when the data is distributed across many servers and can contain outliers. While there has been a lot of wor…
Local algorithms for interactive clustering
Pranjal Awasthi, Maria-Florina Balcan, Konstantin Voevodski
We study the design of interactive clustering algorithms for data sets satisfying natural stability assumptions. Our algorithms start with any initial clustering and only make loca…
Additive Approximation for Near-Perfect Phylogeny Construction
Pranjal Awasthi, Avrim Blum, Jamie Morgenstern +1
We study the problem of constructing phylogenetic trees for a given set of species. The problem is formulated as that of finding a minimum Steiner tree on points over the Boole…
Center-based Clustering under Perturbation Stability
Pranjal Awasthi, Avrim Blum, Or Sheffet
Clustering under most popular objective functions is NP-hard, even to approximate well, and so unlikely to be efficiently solvable in the worst case. Recently, Bilu and Linial \cit…