research
∙
07/10/2023
Improved Diversity Maximization Algorithms for Matching and Pseudoforest
In this work we consider the diversity maximization problem, where given...
share
research
∙
06/11/2023
Approximation Algorithms for Fair Range Clustering
This paper studies the fair range clustering problem in which the data p...
research
∙
11/01/2022
Composable Coresets for Constrained Determinant Maximization and Beyond
We study the task of determinant maximization under partition constraint...
research
∙
07/16/2022
Adaptive Sketches for Robust Regression with Importance Sampling
We introduce data structures for solving robust regression through stoch...
research
∙
01/26/2021
Sampling a Near Neighbor in High Dimensions – Who is the Fairest of Them All?
Similarity search is a fundamental algorithmic primitive, widely used in...
research
∙
11/12/2020
Towards Better Approximation of Graph Crossing Number
Graph Crossing Number is a fundamental problem with various applications...
research
∙
07/07/2020
Streaming Complexity of SVMs
We study the space complexity of solving the bias-regularized SVM proble...
research
∙
04/23/2020
Non-Adaptive Adaptive Sampling on Turnstile Streams
Adaptive sampling is a useful algorithmic tool for data summarization pr...
research
∙
02/17/2020
(Individual) Fairness for k-Clustering
We give a local search based algorithm for k-median (k-means) clustering...
research
∙
07/06/2019
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
"Composable core-sets" are an efficient framework for solving optimizati...
research
∙
06/06/2019
Near Neighbor: Who is the Fairest of Them All?
In this work we study a fair variant of the near neighbor problem. Namel...
research
∙
02/10/2019
Set Cover in Sub-linear Time
We study the classic set cover problem from the perspective of sub-linea...
research
∙
11/08/2018
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
We introduce and study the notion of an outer bi-Lipschitz extension of ...
research
∙
07/31/2018