# Solving sampling problems with circuits?

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?

• 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
May 21, 2022 at 0:01
• @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? May 21, 2022 at 0:22
• 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
May 21, 2022 at 1:18