4 citations · 9 across the 7 of their papers we have counts for
8 papers · 1 filter
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…
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…
Improved Space Bounds for Learning with Experts
Anders Aamand, Justin Y. Chen, Huy Lê Nguyen +1
We give improved tradeoffs between space and regret for the online learning with expert advice problem over days with experts. Given a space budget of for $δ\in (0,1)…
Faster Fundamental Graph Algorithms via Learned Predictions
Justin Y. Chen, Sandeep Silwal, Ali Vakilian +1
We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or si…
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
Justin Y. Chen, Shyam Narayanan, Yinzhan Xu
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea…