research
∙
09/08/2023
Parallel Submodular Function Minimization
We consider the parallel complexity of submodular function minimization ...
share
research
∙
06/16/2023
Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs
In this paper we describe a randomized algorithm which returns a maximal...
research
∙
04/03/2023
A d^1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids
Monotonicity testing of Boolean functions on the hypergrid, f:[n]^d →{0,...
research
∙
11/10/2022
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an O(n√(d)) Monotonicity Tester
The problem of testing monotonicity for Boolean functions on the hypergr...
research
∙
07/09/2022
Improved Lower Bounds for Submodular Function Minimization
We provide a generic technique for constructing families of submodular f...
research
∙
06/30/2022
Approximation Algorithms for Continuous Clustering and Facility Location Problems
We consider the approximability of center-based clustering problems wher...
research
∙
11/14/2021
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection
Submodular function minimization (SFM) and matroid intersection are fund...
research
∙
06/23/2021
Better Algorithms for Individually Fair k-Clustering
We study data clustering problems with ℓ_p-norm objectives (e.g. k-Media...
research
∙
03/04/2021
Revisiting Priority k-Center: Fairness and Outliers
In the Priority k-Center problem, the input consists of a metric space (...
research
∙
02/23/2021
Robust k-Center with Two Types of Radii
In the non-uniform k-center problem, the objective is to cover points in...
research
∙
07/12/2020
Graph Connectivity and Single Element Recovery via Linear and OR Queries
We study the problem of finding a spanning forest in an undirected, n-ve...
research
∙
11/25/2019
Faster Matroid Intersection
In this paper we consider the classic matroid intersection problem: give...
research
∙
10/30/2019
On a Decentralized (Δ+1)-Graph Coloring Algorithm
We consider a decentralized graph coloring model where each vertex only ...
research
∙
04/30/2019
Simpler and Better Algorithms for Minimum-Norm Load Balancing
Recently, Chakrabarty and Swamy (STOC 2019) introduced the minimum-norm...
research
∙
01/08/2019
Fair Algorithms for Clustering
We study clustering problems under the lens of algorithmic fairness ins...
research
∙
11/12/2018
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
In many optimization problems, a feasible solution induces a multi-dime...
research
∙
11/04/2018
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
We describe a Õ(d^5/6)-query monotonicity tester for Boolean functions f...
research
∙
11/04/2018
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions on Hypergrids
Testing monotonicity of Boolean functions over the hypergrid, f:[n]^d →{...
research
∙
05/06/2018
Generalized Center Problems with Outliers
We study the F-center problem with outliers: given a metric space (X,d),...
research
∙
01/09/2018
Adaptive Boolean Monotonicity Testing in Total Influence Time
The problem of testing monotonicity of a Boolean function f:{0,1}^n →{0,...
research
∙
01/09/2018
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling
Given a non-negative n × m real matrix A, the matrix scaling problem is...
research
∙
11/23/2017
Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median
We consider a generalization of k-median and k-center, called the order...
research
∙
11/12/2017
Dynamic Algorithms for Graph Coloring
We design fast dynamic algorithms for proper vertex and edge colorings i...
research
∙
10/29/2017