17 citations · 24 across the 15 of their papers we have counts for
7 papers · 1 filter
How fast can you find a good hypothesis?
Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen +1
In the hypothesis selection problem, we are given sample and query access to finite set of candidate distributions (hypotheses), , and samples f…
Breaking the Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been mad…
On the Structure of Replicable Hypothesis Testers
Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen +2
A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defin…
Improved Approximations for Hard Graph Problems using Predictions
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi +2
We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the…
Differentially Private Quantiles with Smaller Error
Jacob Imola, Fabrizio Boninsegna, Hannah Keller +3
In the approximate quantiles problem, the goal is to output quantile estimates, the ranks of which are as close as possible to given quantiles $0 \leq q_1 \leq\dots \leq q_…
Learning-Augmented Frequent Directions
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi +2
An influential paper of Hsu et al. (ICLR'19) introduced the study of learning-augmented streaming algorithms in the context of frequency estimation. A fundamental problem in the st…