Open Problems:85 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Sample Stretching to Open Problems:85 without leaving a redirect

2017-11-08T15:25:07Z

Krzysztof Onak moved page Waiting:Sample Stretching to Open Problems:85 without leaving a redirect

Krzysztof Onak: Cleaning the header, small changes

2017-11-08T15:24:44Z

Cleaning the header, small changes

Ccanonne at 19:58, 20 October 2017

2017-10-20T19:58:30Z

Ccanonne: 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..."

2017-10-20T19:58:06Z

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..."

New page

{{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., $\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_Problems:69|Open Problem 69]], and the setting of sampling correctors/improvers {{cite|CanonneGR-16}}.

← Older revision	Revision as of 15:25, 8 November 2017
(No difference)

@@ Line 2: / Line 2: @@
 |source=focs17
 |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.
-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$?
+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]], and the setting of sampling correctors/improvers {{cite|CanonneGR-16}}.
+''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}}.