research
∙
06/20/2023
Data Structures for Density Estimation
We study statistical/computational tradeoffs for the following density e...
share
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 ...
research
∙
03/02/2023
Improved Space Bounds for Learning with Experts
We give improved tradeoffs between space and regret for the online learn...
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...
research
∙
07/18/2022
Streaming Algorithms for Support-Aware Histograms
Histograms, i.e., piece-wise constant approximations, are a popular tool...
research
∙
04/26/2022
Faster Fundamental Graph Algorithms via Learned Predictions
We consider the question of speeding up classic graph algorithms with ma...
research
∙
04/05/2022
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
We revisit the problem of privately releasing the all-pairs shortest pat...
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 ...
research
∙
10/21/2021
Online Bipartite Matching with Predicted Degrees
We propose a model for online graph problems where algorithms are given ...
research
∙
11/09/2019