Problem \[prob:dict to maj\] would have applications to lower bounds for sampling in ${\mathbf{AC^{0}}}$; even a weaker claim, where the right hand side in Equation  is replaced with $\omega(1)$, would have implications for sampling in the lower class ${\mathbf{NC^{0}}}$. We discuss this further in Section \[sec:motivation\].

Arguably, the simplest and most natural bijection $\varphi \colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$ to consider is the following. $$\varphi(x) = \left\{
\begin{array}{ll}
 {\sf flip}(x) \circ 1 & \text{\quad if $|x| \le n/2$}  \\
 x \circ 0 & \text{\quad otherwise},
\end{array}
\right.$$ where ${\sf flip}(x)$ denotes the bit-wise complement of $x$. It is straightforward to verify that ${{\sf avgStretch}}(\varphi) = \Theta(\sqrt{n})$. To see this, note that any edge $(x,y)$ in ${\{0,1\}^{n}}$, where $|x| = n/2$ and $|y| = n/2+1$, contributes $n$ to the average stretch, whereas all other edges contribute $1$. The assertion then follows since $\Theta(1/\sqrt{n})$ fraction of the edges are of the first type. In fact, the maximum stretch of $\varphi$ is $n$, where $${{\sf maxStretch}}(\varphi) = \max_{\substack{x \in {\{0,1\}^{n}}\\ i \in  [n]}} {{\sf distance}}(\varphi(x),\varphi(x+e_i)).$$ As far as we know, prior to our work this simple bijection achieved the best-known upper bound on the average stretch between ${\{0,1\}^{n}}$ and ${\mathcal{B}_{n}}$, and no non-trivial upper bounds 