research
∙
04/05/2023
Optimal Sketching Bounds for Sparse Linear Regression
We study oblivious sketching for k-sparse linear regression under variou...
share
research
∙
02/13/2023
Sparse Dimensionality Reduction Revisited
The sparse Johnson-Lindenstrauss transform is one of the central techniq...
research
∙
02/06/2023
Optimally Interpolating between Ex-Ante Fairness and Welfare
For the fundamental problem of allocating a set of resources among indiv...
research
∙
11/15/2022
Improved Coresets for Euclidean k-Means
Given a set of n points in d dimensions, the Euclidean k-means problem (...
research
∙
09/28/2022
Adaptive Out-Orientations with Applications
We give simple algorithms for maintaining edge-orientations of a fully-d...
research
∙
09/05/2022
The Power of Uniform Sampling for Coresets
Motivated by practical generalizations of the classic k-median and k-mea...
research
∙
07/11/2022
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
The Uncapacitated Facility Location (UFL) problem is one of the most fun...
research
∙
07/03/2022
An Empirical Evaluation of k-Means Coresets
Coresets are among the most popular paradigms for summarizing data. In p...
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
∙
02/25/2022
Towards Optimal Lower Bounds for k-median and k-means Coresets
Given a set of points in a metric space, the (k,z)-clustering problem co...
research
∙
08/19/2021
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an a...
research
∙
04/13/2021
A New Coreset Framework for Clustering
Given a metric space, the (k,z)-clustering problem consists of finding k...
research
∙
02/18/2020
Fair Clustering with Multiple Colors
A fair clustering instance is given a data set A in which every point is...
research
∙
02/14/2020
Algorithms for Fair Team Formation in Online Labour Marketplaces
As freelancing work keeps on growing almost everywhere due to a sharp de...
research
∙
05/31/2019
Principal Fairness: Removing Bias via Projections
Reducing hidden bias in the data and ensuring fairness in algorithmic da...
research
∙
04/12/2019
Maximizing Online Utilization with Commitment
We investigate online scheduling with commitment for parallel identical ...
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
∙
05/22/2018