
-
Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
We investigate the problem of exact cluster recovery using oracle querie...
read it
-
Spectral Clustering Oracles in Sublinear Time
Given a graph G that can be partitioned into k disjoint expanders with o...
read it
-
Fast and Accurate k-means++ via Rejection Sampling
k-means++ <cit.> is a widely used clustering algorithm that is easy to i...
read it
-
Consistent k-Clustering for General Metrics
Given a stream of points in a metric space, is it possible to maintain a...
read it
-
Secretaries with Advice
The secretary problem is probably the purest model of decision making un...
read it
-
On Mean Estimation for Heteroscedastic Random Variables
We study the problem of estimating the common mean μ of n independent sy...
read it
-
InstantEmbedding: Efficient Local Node Representations
In this paper, we introduce InstantEmbedding, an efficient method for ge...
read it
-
Sliding Window Algorithms for k-Clustering Problems
The sliding window model of computation captures scenarios in which data...
read it
-
Fully Dynamic Algorithm for Constrained Submodular Optimization
The task of maximizing a monotone submodular function under a cardinalit...
read it
-
Exact Recovery of Mangled Clusters with Same-Cluster Queries
We study the problem of recovering distorted clusters in the semi-superv...
read it
-
Dynamic Algorithms for the Massively Parallel Computation Model
The Massive Parallel Computing (MPC) model gained popularity during the ...
read it
-
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
read it
-
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...
read it
-
Parallel and Streaming Algorithms for K-Core Decomposition
The k-core decomposition is a fundamental primitive in many machine lear...
read it
-
Fair Clustering Through Fairlets
We study the question of fair clustering under the disparate impact doc...
read it
-
ASYMP: Fault-tolerant Mining of Massive Graphs
We present ASYMP, a distributed graph processing system developed for th...
read it
-
One-Shot Coresets: The Case of k-Clustering
Scaling clustering algorithms to massive data sets is a challenging task...
read it
-
Local Graph Clustering Beyond Cheeger's Inequality
Motivated by applications of large-scale graph clustering, we study rand...
read it