11 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…
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…
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…