function, and the indicator of ${\mathcal{B}_{n}}\subset {\{0,1\}^{n+1}}$ is the *majority* function, and it is a recurring theme in the analysis of Boolean functions that they are, in some senses, opposites of one another.

Lovett and Viola [@LV11] suggested to utilize the opposite structure of the Boolean cube and the Hamming ball for proving lower bounds on sampling by low-level complexity classes such as ${\mathbf{AC^{0}}}$ and ${\mathbf{TC^{0}}}$. In particular, Lovett and Viola were interested in proving that for any even $n$, any bijection $f \colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$ has a large average stretch, where $${{\sf avgStretch}}(f) = {\mathop{{\bf E}\/}}_{\substack{x \sim {\{0,1\}^{n}}\\ i \sim  [n]}} \left[ {{\sf distance}}(f(x),f(x+e_i)) \right],$$ and ${{\sf distance}}(\cdot,\cdot)$ denotes the Hamming distance. To be more precise, Lovett and Viola raised the following open problem.

\[prob:dict to maj\] Let $n \in {{\mathbb N}}$ be an even integer. Prove that for any bijection $f \colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$, it holds that $$\label{eq:superpolylog stretch}
{{\sf avgStretch}}(f) = (\log{n})^{\omega(1)}.$$

A positive answer to Problem \[prob:dict to maj\] would demonstrate yet another scenario in which the Boolean cube and the Hamming ball have a different geometric structure – any bijection from the former to the latter does not respect distances. Furthermore, a positive answer to 