$n \in {{\mathbb N}}$ be odd. Does there exist a bijection $h \colon {\{0,1\}^{n}}\to \{ (x,{{\sf majority}}(x)) \colon x \in {\{0,1\}^{n}}\}$ such that each output bit of $h$ is computable in ${\mathbf{AC^{0}}}$?

Note that a positive answer to Problem \[problem:embedding into majset\] implies a positive answer to Problem \[problem:embedding into (x,maj(x))\]. Indeed, if $g \colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$ is an embedding from Problem \[problem:embedding into majset\], then the function $h \colon {\{0,1\}^{n+1}} \to {\{0,1\}^{n+2}}$ defined as $$h(x_1, \dots, x_n,x_{n+1}) =
                    \begin{cases}
                        g(x_1,\dots,x_n) \circ 1 & \text{\quad $x_{n+1} = 1$} \\
                        {\sf flip}(g(x_1,\dots,x_n)) \circ 0 & \text{\quad $x_{n+1} = 0$} \\
                    \end{cases}$$ gives an embedding for Problem \[problem:embedding into (x,maj(x))\]. Therefore, a negative answer to Problem \[problem:embedding into (x,maj(x))\] implies a negative answer to Problem \[problem:embedding into majset\]. In the other direction, if a function $h \colon {\{0,1\}^{n}}\to \{ (x,{{\sf majority}}(x)) \colon x \in {\{0,1\}^{n}}\}$ gives a positive answer to Problem \[problem:embedding into (x,maj(x))\], then the function $g \colon {\{0,1\}^{n}}\to {\{0,1\}^{n}}$ defined as[^5] $$g(x_1, \dots, x_n) =
                    \begin{cases}
                        (h(x_1,\dots,x_n))_{[1,\dots,n]}            & \text{\quad} (h(x_1,\dots,x_n))_{n+1} = 1 \\
                        {\sf flip}(h(x_1,\dots,x_n))_{[1,\dots,n]}  & \text{\quad otherwise} \\
                    \end{cases}$$ samples ${\mathcal{B}_{n-1}}$ using input of length $n$, which almost[^6] answers Problem \[problem:embedding into (x,maj(x))\].

On the positive side, Viola [@Vi12] 