Difference between revisions of "Open Problems:85"
m (Krzysztof Onak moved page Waiting:Sample Stretching to Open Problems:85 without leaving a redirect) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 2: | Line 2: | ||
|source=focs17 | |source=focs17 | ||
|who=Ryan O'Donnell | |who=Ryan O'Donnell | ||
| − | |||
}} | }} | ||
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. | 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 | + | What is the minimum value of $\varepsilon\in(0,1]$ such that there exists an algorithm that, 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_Problems:69|Open Problem 69]] | + | ''Note:'' this is of a similar spirit as [[Open_Problems:69|Open Problem 69]] and the setting of sampling correctors and improvers {{cite|CanonneGR-16}}. |
Latest revision as of 15:25, 8 November 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 that, 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 and improvers [CanonneGR-16].
