58 citations · 82 across the 8 of their papers we have counts for
9 papers · 1 filter
Triangle and Four Cycle Counting with Predictions in Graph Streams
Justin Y. Chen, Talya Eden, Piotr Indyk +7
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in…
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 \…
Scalable Nearest Neighbor Search for Optimal Transport
Arturs Backurs, Yihe Dong, Piotr Indyk +2
The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity…
Sample-Optimal Low-Rank Approximation of Distance Matrices
Piotr Indyk, Ali Vakilian, Tal Wagner +1
A distance matrix represents all pairwise distances, , between two point sets and in an arbit…
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…
Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths +5
We consider the problem of determining the maximal such that every matching of size (or at most ) in a bipartite graph contains an induced matching of s…