3
$\begingroup$

Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^{\mathsf{poly}(n)};\; S(r))$. Let's call such an $S$ a sampler for $D$.

Question

Is it possible to pseduodeterministically (in the sense of e.g., this paper) choose an element from the support of $D_n$ in sub-exponential time? I.e., is there a probabilistic sub-exponential time algorithm $C$ ($C$ for choice) with the following properties:

  1. For any two samplers $S_1, S_2$ of $D$ we have $C(S_1, 1^n) = C(S_2, 1^n)$ with noticeable probability.
  2. For any sampler $S$ for $D$, $C(S, 1^n)$ is in the support of $D_n$ for all $n$.

It would still be interesting if property 1 were weakened to "with non-negligible probability" and 2 were weakened to "for infinitely many $n$".

Please feel free to make any plausible complexity-theoretic assumptions.

Some motivation

You can think of $C$ as a kind of canonical-choice algorithm. Note that constructing the above is at least as hard as giving a sub-exponential time algorithm for graph isomorphism, since given a graph $G$ we can easily construct a sampler for a distribution supported on the isomorphism class of $G$ that does not depend on the choice of $G$. To test if two graphs are isomorphic we feed these two distributions into our chooser $C$ and check to see if the canonical representatives output by $C$ are equal.

$\endgroup$

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.