4 papers
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…
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…