8 papers
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…
Towards Tight Bounds for Streaming Attention
Justin Y. Chen, Ying Feng, Piotr Indyk +3
The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In partic…
Skirting Additive Error Barriers for Private Turnstile Streams
Anders Aamand, Justin Y. Chen, Sandeep Silwal
We study differentially private continual release of the number of distinct items in a turnstile stream, where items may be both inserted and deleted. A recent work of Jain, Kalema…
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…
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…
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…