distribution $(x,b(x)) \in {\{0,1\}^{n+1}}$ cannot be generated by ${{\rm poly}}(n)$-size ${\mathbf{AC^{0}}}$ circuits given random bits as input.

Note that the challenge does not specify the input length. Obviously, the input length should be at least $n$, since this is the entropy of $(x,b(x))$, and the challenge becomes harder as the input length increases. In this paper we only consider distributions ${{\mathcal D}}$ that are uniform over subsets $A {\subseteq}{\{0,1\}^{n}}$ of size $|A| = 2^m$ for some $m \in {{\mathbb N}}$, and functions with input length $m$ sampling ${{\mathcal D}}$ (rather than approximating ${{\mathcal D}}$). Therefore, in this setting, the question of sampling a distribution ${{\mathcal D}}$ reduces to finding a bijection from ${\{0,1\}^{m}}$ to $A$ such that each bit of the bijection is efficiently computable.

As a concrete candidate for the map $b \colon {\{0,1\}^{n}}\to \{0,1\}$ in Challenge \[challenge:main\], Viola suggested to use ${{\sf majority}}$ – the other notoriously hard function for ${\mathbf{AC^{0}}}$ other than ${{\sf parity}}$. The following two problems have been stated in [@LV11].

\[problem:embedding into majset\] Let $n \in {{\mathbb N}}$ be even. Does there exist a bijection $g \colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$ such that each output bit of $g$ is computable in ${\mathbf{AC^{0}}}$?

\[problem:embedding into (x,maj(x))\] Let 