3 papers
cs.DS2025
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…
cs.DS2024
Near-Optimal Trace Reconstruction for Mildly Separated Strings
Anders Aamand, Allen Liu, Shyam Narayanan
In the trace reconstruction problem our goal is to learn an unknown string given independent traces of . A trace is obtained by independently deleting each bit…
cs.DS2024
Statistical-Computational Trade-offs for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +4
We study the density estimation problem defined as follows: given distributions over a discrete domain , as well as a collection of samples chosen from…