0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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, 2022 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$
    – trillianhaze
    May 21, 2022 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, 2022 at 1:18

0

Reset to default

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.