Difference between revisions of "Open Problems:85"
(Created page with "{{Header |source=focs17 |who=Ryan O'Donnell |title=Sample Stretching }} Let $p$ be an unknown (discrete) probability distribution over a discrete domain $\Omega$ (e.g., $\Ome...") |
(No difference)
|
Revision as of 19:58, 20 October 2017
Suggested by | Ryan O'Donnell |
---|---|
Source | FOCS 2017 |
Short link | https://sublinear.info/85 |
Let $p$ be an unknown (discrete) probability distribution over a discrete domain $\Omega$ (e.g., $\Omega=[n]$) and $k\in\mathbb{N}$. As usual, $\operatorname{d}_{\rm TV}$ denotes the total variation distance.
What is the minimum value of $\varepsilon\in(0,1]$ such that there exists an algorithm, which, on input $k$ i.i.d. samples from $p$, outputs $k+1$ i.i.d. samples from some $p'$ such that $\operatorname{d}_{\rm TV}(p,p')\leq \varepsilon$?
Note: this is of a similar spirit as Open Problem 69, and the setting of sampling correctors/improvers [CanonneGR-16].