209 citations · 560 across the 53 of their papers we have counts for
59 papers
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions
Justin Y. Chen, Piotr Indyk, David P. Woodruff
We revisit the problem of estimating the profile (also known as the rarity) in the data stream model. Given a sequence of elements from a universe of size , its profile is a…
A Near-Linear Time Algorithm for the Chamfer Distance
Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram +2
For any two point sets of size up to , the Chamfer distance from to is defined as , whe…
Data Structures for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +3
We study statistical/computational tradeoffs for the following density estimation problem: given distributions over a discrete domain of size , and sampli…
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
Nicholas Schiefer, Justin Y. Chen, Piotr Indyk +3
An -approximate quantile sketch over a stream of inputs approximates the rank of any query point - that is, the number of input points less than - up to an…
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Anders Aamand, Justin Y. Chen, Piotr Indyk +5
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph…
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Ainesh Bakshi, Piotr Indyk, Praneeth Kacham +2
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel…