research
∙
08/20/2023
Improved Differentially Private Densest Subgraph: Local and Purely Additive
We study the Densest Subgraph problem under the additional constraint of...
share
research
∙
05/31/2023
Fully Dynamic Submodular Maximization over Matroids
Maximizing monotone submodular functions under a matroid constraint is a...
research
∙
10/25/2022
Efficient and Stable Fully Dynamic Facility Location
We consider the classic facility location problem in fully dynamic data ...
research
∙
09/08/2022
Active Learning of Classifiers with Label and Seed Queries
We study exact active learning of binary and multiclass classifiers with...
research
∙
08/16/2022
Deletion Robust Non-Monotone Submodular Maximization over Matroids
Maximizing a submodular function is a fundamental task in machine learni...
research
∙
06/17/2022
Scalable Differentially Private Clustering via Hierarchically Separated Trees
We study the private k-median and k-means clustering problem in d dimens...
research
∙
03/02/2022
Near-Optimal Correlation Clustering with Privacy
Correlation clustering is a central problem in unsupervised learning, wi...
research
∙
01/31/2022
Deletion Robust Submodular Maximization over Matroids
Maximizing a monotone submodular function is a fundamental task in machi...
research
∙
12/01/2021
Efficient and Local Parallel Random Walks
Random walks are a fundamental primitive used in many machine learning a...
research
∙
06/15/2021
Correlation Clustering in Constant Many Parallel Rounds
Correlation clustering is a central topic in unsupervised learning, with...
research
∙
06/09/2021
On Margin-Based Cluster Recovery with Oracle Queries
We study an active cluster recovery problem where, given a set of n poin...
research
∙
01/31/2021
Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
We investigate the problem of exact cluster recovery using oracle querie...
research
∙
01/14/2021
Spectral Clustering Oracles in Sublinear Time
Given a graph G that can be partitioned into k disjoint expanders with o...
research
∙
12/22/2020
Fast and Accurate k-means++ via Rejection Sampling
k-means++ <cit.> is a widely used clustering algorithm that is easy to i...
research
∙
11/13/2020
Consistent k-Clustering for General Metrics
Given a stream of points in a metric space, is it possible to maintain a...
research
∙
11/13/2020
Secretaries with Advice
The secretary problem is probably the purest model of decision making un...
research
∙
10/22/2020
On Mean Estimation for Heteroscedastic Random Variables
We study the problem of estimating the common mean μ of n independent sy...
research
∙
10/14/2020
InstantEmbedding: Efficient Local Node Representations
In this paper, we introduce InstantEmbedding, an efficient method for ge...
research
∙
06/10/2020
Sliding Window Algorithms for k-Clustering Problems
The sliding window model of computation captures scenarios in which data...
research
∙
06/08/2020
Fully Dynamic Algorithm for Constrained Submodular Optimization
The task of maximizing a monotone submodular function under a cardinalit...
research
∙
06/08/2020
Exact Recovery of Mangled Clusters with Same-Cluster Queries
We study the problem of recovering distorted clusters in the semi-superv...
research
∙
05/22/2019
Dynamic Algorithms for the Massively Parallel Computation Model
The Massive Parallel Computing (MPC) model gained popularity during the ...
research
∙
05/05/2019
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
research
∙
05/02/2019
Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
Streaming algorithms are generally judged by the quality of their soluti...
research
∙
08/07/2018
Parallel and Streaming Algorithms for K-Core Decomposition
The k-core decomposition is a fundamental primitive in many machine lear...
research
∙
02/15/2018
Fair Clustering Through Fairlets
We study the question of fair clustering under the disparate impact doc...
research
∙
12/28/2017
ASYMP: Fault-tolerant Mining of Massive Graphs
We present ASYMP, a distributed graph processing system developed for th...
research
∙
11/27/2017
One-Shot Coresets: The Case of k-Clustering
Scaling clustering algorithms to massive data sets is a challenging task...
research
∙
04/30/2013