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:
- 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.
- 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.
