58 citations · 65 across the 5 of their papers we have counts for
7 papers · 1 filter
Faster Kernel Matrix Algebra via Density Estimation
Arturs Backurs, Piotr Indyk, Cameron Musco +1
We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix corresponding to points $x_1,\ldots,x_n \…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
Scalable Fair Clustering
Arturs Backurs, Piotr Indyk, Krzysztof Onak +3
We study the fair variant of the classic -median problem introduced by Chierichetti et al. [2017]. In the standard -median problem, given an input pointset , the goal is t…
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal +2
Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter ex…
Fast Modular Subset Sum using Linear Sketching
Kyriakos Axiotis, Arturs Backurs, Christos Tzamos
Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum…
Tight Hardness Results for Maximum Weight Rectangles
Arturs Backurs, Nishanth Dikkala, Christos Tzamos
Given weighted points (positive or negative) in dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorith…