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?

  • $\begingroup$ 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. $\endgroup$
    – usul
    May 21 at 0:01
  • $\begingroup$ @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? $\endgroup$ May 21 at 0:22
  • 2
    $\begingroup$ 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. $\endgroup$
    – usul
    May 21 at 1:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.