  Let $A \subseteq \{0,1\}^n$ be a set of size $2^{n-1}$, and let $\phi \colon
\{0,1\}^{n-1} \to A$ be a bijection. We define the average stretch of $\phi$ as
${\sf avgStretch}(\phi) = {\mathbb E}[{\sf dist}(\phi(x),\phi(x'))]$, where the
expectation is taken over uniformly random $x,x' \in \{0,1\}^{n-1}$ that differ
in exactly one coordinate. In this paper we continue the line of research
studying mappings on the discrete hypercube with small average stretch. We
prove the following results.
  (1) For any set $A \subseteq \{0,1\}^n$ of density $1/2$ there exists a
bijection $\phi_A \colon \{0,1\}^{n-1} \to A$ such that ${\sf
avgstretch}(\phi_A) = O(\sqrt{n})$.
  (2) For $n = 3^k$ let $A_{{\sf rec\text{-}maj}} = \{x \in \{0,1\}^n : {\sf
rec\text{-}maj}(x) = 1\}$, where ${\sf rec\text{-}maj} : \{0,1\}^n \to \{0,1\}$
is the function recursive majority of 3's. There exists a bijection $\phi_{{\sf
rec\text{-}maj}} \colon \{0,1\}^{n-1} \to A_{\sf rec\text{-}maj}$ such that
${\sf avgstretch}(\phi_{\sf rec\text{-}maj}) = O(1)$.
  (3) Let $A_{\sf tribes} = \{x \in \{0,1\}^n : {\sf tribes}(x) = 1\}$. There
exists a bijection $\phi_{{\sf tribes}} \colon \{0,1\}^{n-1} \to A_{\sf
tribes}$ such that ${\sf avgstretch}(\phi_{{\sf tribes}}) = O(\log(n))$.
  These results answer the questions raised by Benjamini et al.\ (FOCS 2014).
