Problem 85: Sample Stretching

From Open Problems in Sublinear Algorithms
Revision as of 15:25, 8 November 2017 by Krzysztof Onak (talk | contribs) (Krzysztof Onak moved page Waiting:Sample Stretching to Open Problems:85 without leaving a redirect)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
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].