<p>If I allow a circuit family (say, poly size, polylog depth) poly(<span class="math-container">$n$</span>) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the criterion for &quot;solving a sampling problem&quot; in this case should be.</p>
<p>To elaborate: Given a BPP machine <span class="math-container">$M$</span>, we say <span class="math-container">$M$</span> <em>solves</em> the sampling problem <span class="math-container">$S = (D_x)_{x \in \{0,1\}^*}$</span> (each <span class="math-container">$D_x$</span> a distribution over poly(<span class="math-container">$|x|$</span>) bits) iff for all <span class="math-container">$x \in \{0,1\}^*$</span> and for all <span class="math-container">$\epsilon &gt; 0$</span> the input <span class="math-container">$\langle x, 0^{1/\epsilon} \rangle$</span> implies
<span class="math-container">$$
\|M(x, 0^{1/\epsilon}) - D_x\| \leq \epsilon,
$$</span>
where <span class="math-container">$\|\cdot\|$</span> is usually the total variation distance. I'm curious if there is an agreed-upon extension of this definition to circuits with randomized advice.</p>
<p>One (flawed) definition is: a circuit family <span class="math-container">$\{C_{n + r}\}_{n \in \mathbb{N}}$</span> with <span class="math-container">$r = \text{poly}(n)$</span> bits of randomized advice <em>solves</em> the sampling problem <span class="math-container">$S$</span> iff for all <span class="math-container">$x \in \{0,1\}^*$</span> and for all <span class="math-container">$\epsilon &gt; 0$</span> the input <span class="math-container">$\langle x, 0^{1/\epsilon}, r_1, \dots, r_{\text{poly}(|x|)}\rangle$</span> implies
<span class="math-container">$$
\|C(x, 0^{1/\epsilon}, r_1, \dots, r_{\text{poly}(|x|)}) - D_x\| \leq \epsilon.
$$</span>
However, a definition like this seems pointless because I can always just absorb the <span class="math-container">$0^{1/\epsilon}$</span> into the advice string. And plus it's another matter how the number of output bits is influenced by <span class="math-container">$\epsilon$</span>. Any ideas?</p>

CC BY-SA 4.0
2022-05-21T00:01:47.677Z
I'm a bit confused -- in the BPP setting, I believe the point of the $0^{1/\epsilon}$ is just to enforce that the algorithm run in time poly$(1/\epsilon)$. In the circuit setting, it doesn't seem to do anything. It also doesn't seem to hurt, so I'm not sure what the problem is.
usul
CC BY-SA 4.0
2022-05-21T00:22:20.113Z
@usul Hmm I always interpreted the $0^{1/\epsilon}$ as a unary encoding of "how accurate you want to be". You're obviously right that in BPP that amounts to a poly($1/\epsilon$) overhead. But if I want to "tell" a circuit how accurate I want to be ("within $\epsilon$") of sampling from some distribution, then I don't see an obvious definition. But maybe my understanding of the $0^{1/\epsilon}$ is just wrong?
trillianhaze
CC BY-SA 4.0
2022-05-21T01:18:15.907Z
Oh, you're right that it does that too. But oh, you probably do want to revisit the definitions of circuit family. Here you kind of have a blend of circuits and TMs with advice. A circuit family doesn't need an advice string at all because for each size, there is a new circuit of that size (which could have some advice hardcoded). And for a TM with advice, note it should be a fixed advice string for all inputs of a given size.
usul
<reference-request><circuits><sampling>
Solving sampling problems with circuits?
trillianhaze
# Solving sampling problems with circuits?

(Asked by: username_0 on 2022-05-20)

If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the criterion for "solving a sampling problem" in this case should be.

To elaborate: Given a BPP machine $M$, we say $M$ *solves* the sampling problem $S = (D\_x)\_{x \in \{0,1\}^\*}$ (each $D\_x$ a distribution over poly($|x|$) bits) iff for all $x \in \{0,1\}^\*$ and for all $\epsilon > 0$ the input $\langle x, 0^{1/\epsilon} \rangle$ implies
$$
\|M(x, 0^{1/\epsilon}) - D\_x\| \leq \epsilon,
$$
where $\|\cdot\|$ is usually the total variation distance. I'm curious if there is an agreed-upon extension of this definition to circuits with randomized advice.

One (flawed) definition is: a circuit family $\{C\_{n + r}\}\_{n \in \mathbb{N}}$ with $r = \text{poly}(n)$ bits of randomized advice *solves* the sampling problem $S$ iff for all $x \in \{0,1\}^\*$ and for all $\epsilon > 0$ the input $\langle x, 0^{1/\epsilon}, r\_1, \dots, r\_{\text{poly}(|x|)}\rangle$ implies
$$
\|C(x, 0^{1/\epsilon}, r\_1, \dots, r\_{\text{poly}(|x|)}) - D\_x\| \leq \epsilon.
$$
However, a definition like this seems pointless because I can always just absorb the $0^{1/\epsilon}$ into the advice string. And plus it's another matter how the number of output bits is influenced by $\epsilon$. Any ideas?

**Tags:** reference-request, circuits, sampling
> **Comments:**
> **username_1**: I'm a bit confused -- in the BPP setting, I believe the point of the $0^{1/\epsilon}$ is just to enforce that the algorithm run in time poly$(1/\epsilon)$. In the circuit setting, it doesn't seem to do anything. It also doesn't seem to hurt, so I'm not sure what the problem is.  
> **username_0**: @usul Hmm I always interpreted the $0^{1/\epsilon}$ as a unary encoding of "how accurate you want to be". You're obviously right that in BPP that amounts to a poly($1/\epsilon$) overhead. But if I want to "tell" a circuit how accurate I want to be ("within $\epsilon$") of sampling from some distribution, then I don't see an obvious definition. But maybe my understanding of the $0^{1/\epsilon}$ is just wrong?  
> **username_1**: Oh, you're right that it does that too. But oh, you probably do want to revisit the definitions of circuit family. Here you kind of have a blend of circuits and TMs with advice. A circuit family doesn't need an advice string at all because for each size, there is a new circuit of that size (which could have some advice hardcoded). And for a TM with advice, note it should be a fixed advice string for all inputs of a given size.  

---

## 0 answers

