15 citations · 36 across the 25 of their papers we have counts for
21 papers · 1 filter
Adversarially Robust Approximate Furthest Neighbor
Kiarash Banihashem, Jeff Giliberti, Prashant Gokhale +5
We work in the adaptive query model, where one is given a point set and seeks to construct a data structure that can answer correctly and efficiently a seq…
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…
Robust Streaming Against Low-Memory Adversaries
Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal
Robust streaming, the study of streaming algorithms that provably work when the stream is generated by an adaptive adversary, has seen tremendous progress in recent years. However,…
Dimension Reduction for Clustering: The Curious Case of Discrete Centers
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir +2
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of points into dimension with low…
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…