research
∙
12/29/2022
Constant Approximation for Normalized Modularity and Associations Clustering
We study the problem of graph clustering under a broad class of objectiv...
share
research
∙
04/21/2022
Motif Cut Sparsifiers
A motif is a frequently occurring subgraph of a given directed or undire...
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
∙
09/23/2019
A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)
The problem of characterizing testable graph properties (properties that...
research
∙
08/07/2019
Fully dynamic hierarchical diameter k-clustering and k-center
We develop dynamic data structures for maintaining a hierarchical k-cent...
research
∙
05/05/2019
Testable Properties in General Graphs and Random Order Streaming
We present a novel framework closely linking the areas of property testi...
research
∙
12/28/2018
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering
We study fair clustering problems as proposed by Chierichetti et al. Her...
research
∙
11/07/2018
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
One of the most fundamental questions in graph property testing is to ch...
research
∙
09/09/2018
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
We obtain the first strong coresets for the k-median and subspace approx...
research
∙
07/12/2018
Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
We develop and analyze a method to reduce the size of a very large set o...
research
∙
05/22/2018
On Coresets for Logistic Regression
Coresets are one of the central methods to facilitate the analysis of la...
research
∙
12/05/2017
Approximating the Spectrum of a Graph
The spectrum of a network or graph G=(V,E) with adjacency matrix A, cons...
research
∙
11/13/2017
