36 citations · 74 across the 12 of their papers we have counts for
7 papers · 1 filter
Online Coresets for Clustering with Bregman Divergences
Rachit Chhaya, Jayesh Choudhari, Anirban Dasgupta +1
We present algorithms that create coresets in an online setting for clustering problems according to a wide subset of Bregman divergences. Notably, our coresets have a small additi…
On Additive Approximate Submodularity
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar
A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many se…
Saving Critical Nodes with Firefighters is FPT
Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra +1
We consider the problem of firefighting to save a critical subset of nodes. The firefighting game is a turn-based game played on a graph, where the fire spreads to vertices in a br…
A Framework for Estimating Stream Expression Cardinalities
Anirban Dasgupta, Kevin Lang, Lee Rhodes +1
Given distributed data streams , we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over $A_1, \dots,…
A Sparse Johnson--Lindenstrauss Transform
Anirban Dasgupta, Ravi Kumar, Tamás Sarlós
Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work w…
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
Jure Leskovec, Kevin J. Lang, Anirban Dasgupta +1
A large body of work has been devoted to defining and identifying clusters or communities in social and information networks. We explore from a novel perspective several questions…
Sampling Algorithms and Coresets for Lp Regression
Anirban Dasgupta, Petros Drineas, Boulos Harb +2
The Lp regression problem takes as input a matrix $A \in \Real^{n \times d}$, a vector $b \in \Real^n$, and a number , and it returns as output a number ${\cal Z}…