b'Piotr Indyk'

research

∙ 07/06/2023

A Near-Linear Time Algorithm for the Chamfer Distance

For any two point sets A,B ⊂ℝ^d of size up to n, the Chamfer distance fr...

0 Ainesh Bakshi, et al. ∙

research

∙ 06/20/2023

Data Structures for Density Estimation

We study statistical/computational tradeoffs for the following density e...

0 Anders Aamand, et al. ∙

research

∙ 04/15/2023

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

An ε-approximate quantile sketch over a stream of n inputs approximates ...

0 Nicholas Schiefer, et al. ∙

research

∙ 12/01/2022

Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation

Kernel matrices, as well as weighted graphs represented by them, are ubi...

0 Ainesh Bakshi, et al. ∙

research

∙ 11/06/2022

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

Recent work shows that the expressive power of Graph Neural Networks (GN...

0 Anders Aamand, et al. ∙

research

∙ 10/27/2022

Faster Linear Algebra for Distance Matrices

The distance matrix of a dataset X of n points with respect to a distanc...

0 Piotr Indyk, et al. ∙

research

∙ 07/18/2022

Streaming Algorithms for Support-Aware Histograms

Histograms, i.e., piece-wise constant approximations, are a popular tool...

0 Justin Y. Chen, et al. ∙

research

∙ 06/16/2022

Generalization Bounds for Data-Driven Numerical Linear Algebra

Data-driven algorithms can adapt their internal structure or parameters ...

0 Peter Bartlett, et al. ∙

research

∙ 03/17/2022

Triangle and Four Cycle Counting with Predictions in Graph Streams

We propose data-driven one-pass streaming algorithms for estimating the ...

2 Justin Y. Chen, et al. ∙

research

∙ 11/19/2021

Embeddings and labeling schemes for A*

A* is a classic and popular method for graphs search and path finding. I...

1 Talya Eden, et al. ∙

research

∙ 11/06/2021

Frequency Estimation with One-Sided Error

Frequency estimation is one of the most fundamental problems in streamin...

0 Piotr Indyk, et al. ∙

research

∙ 10/21/2021

Online Bipartite Matching with Predicted Degrees

We propose a model for online graph problems where algorithms are given ...

0 Justin Y. Chen, et al. ∙

research

∙ 10/07/2021

Optimal (Euclidean) Metric Compression

We study the problem of representing all distances between n points in ℝ...

0 Piotr Indyk, et al. ∙

research

∙ 07/05/2021

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Random dimensionality reduction is a versatile tool for speeding up algo...

9 Shyam Narayanan, et al. ∙

research

∙ 06/15/2021

Learning-based Support Estimation in Sublinear Time

We consider the problem of estimating the number of distinct elements in...

9 Talya Eden, et al. ∙

research

∙ 02/16/2021

Faster Kernel Matrix Algebra via Density Estimation

We study fast algorithms for computing fundamental properties of a posit...

25 Arturs Backurs, et al. ∙

research

∙ 06/09/2020

Online Page Migration with ML Advice

We consider online algorithms for the page migration problem that use pr...

0 Piotr Indyk, et al. ∙

research

∙ 11/18/2019

Estimating Entropy of Distributions in Constant Space

We consider the task of estimating the entropy of k-ary distributions fr...

0 Jayadev Acharya, et al. ∙

research

∙ 10/30/2019

Learning-Based Low-Rank Approximations

We introduce a "learning-based" algorithm for the low-rank decomposition...

14 Piotr Indyk, et al. ∙

research

∙ 10/09/2019

Scalable Nearest Neighbor Search for Optimal Transport

The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly p...

0 Yihe Dong, et al. ∙

research

∙ 08/14/2019

(Learned) Frequency Estimation Algorithms under Zipfian Distribution

The frequencies of the elements in a data stream are an important statis...

0 Anders Aamand, et al. ∙

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...

0 Piotr Indyk, et al. ∙

research

∙ 06/02/2019

Sample-Optimal Low-Rank Approximation of Distance Matrices

A distance matrix A ∈ R^n × m represents all pairwise distances, A_ij=d(...

0 Piotr Indyk, et al. ∙

research

∙ 02/10/2019

Set Cover in Sub-linear Time

We study the classic set cover problem from the perspective of sub-linea...

0 Piotr Indyk, et al. ∙

research

∙ 02/10/2019

Scalable Fair Clustering

We study the fair variant of the classic k-median problem introduced by ...

0 Arturs Backurs, et al. ∙

research

∙ 01/24/2019

Learning Sublinear-Time Indexing for Nearest Neighbor Search

Most of the efficient sublinear-time indexing algorithms for the high-di...

12 Yihe Dong, et al. ∙

research

∙ 01/24/2019

Learning Space Partitions for Nearest Neighbor Search

Space partitions of R^d underlie a vast and important class of fast near...

0 Yihe Dong, et al. ∙

research

∙ 07/31/2018

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

We study a spectral generalization of classical combinatorial graph span...

0 Piotr Indyk, et al. ∙

research

∙ 06/30/2018

Approximate Nearest Neighbors in Limited Space

We consider the (1+ϵ)-approximate nearest neighbor search problem: given...

0 Piotr Indyk, et al. ∙

research

∙ 06/26/2018

Approximate Nearest Neighbor Search in High Dimensions

The nearest neighbor problem is defined as follows: Given a set P of n p...

0 Alexandr Andoni, et al. ∙

research

∙ 11/05/2017

Practical Data-Dependent Metric Compression with Provable Guarantees

We introduce a new distance-preserving compact representation of multi-d...

0 Piotr Indyk, et al. ∙

research

∙ 04/10/2017

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks

Empirical risk minimization (ERM) is ubiquitous in machine learning and ...

0 Arturs Backurs, et al. ∙

Piotr Indyk

Featured Co-authors