showed an explicit ${\mathbf{AC^{0}}}$ circuit $C \colon \{0,1\}^{{{\rm poly}}(n)} \to \{0,1\}^n$ of size ${{\rm poly}}(n)$ whose output distribution has statistical distance $2^{-n}$ from the uniform distribution on $\{ (x,{{\sf majority}}(x)) \colon x \in {\{0,1\}^{n}}\}$.

Problem \[prob:dict to maj\] was raised by Lovett and Viola [@LV11] in an attempt to prove a lower bound for Problem \[problem:embedding into majset\]. A positive answer to Problem \[prob:dict to maj\] would imply a lower bound for Problem \[problem:embedding into majset\], since by the result of [@Bop], any function $f \colon {\{0,1\}^{n}} \to {\{0,1\}^{n+1}}$ computable by a polynomial size Boolean circuit of constant depth has average stretch at most $\log^{O(1)}(n)$.

As we resolved Problem \[prob:dict to maj\] negatively in a strong sense, it seems that new ideas beyond the sensitivity-based structural results of [@Bop] will be required in order to resolve Problems \[problem:embedding into majset\] and \[problem:embedding into (x,maj(x))\].

Proof Overview {#sec:proof overview for main theorem}
--------------

In this section we describe in high-level the proof of Theorem \[thm:main\]. A full proof is given in Section \[sec:proof of main theorem\]. Let $n \in {{\mathbb N}}$ be an even integer. Our goal is to map ${\{0,1\}^{n}}$ to ${\mathcal{B}_{n}}$ in a way that the two endpoints of 