stronger property.

\[prop:f\_i = x\_i\] For all $i \in [n]$ it holds that $${\mathop{\bf Pr\/}}_{x}[{\psi}_i(x) = x_i] > 1 - O(1/\sqrt{n}).$$

That is, all but the last output bit of ${\psi}$ are essentially determined by a *single* input bit.

#### The complexity of $\boldsymbol{{\psi}}$.

Since the original motivation for constructing ${\psi}$ comes from efficient sampling of distributions, Theorem \[thm:main\] is of larger interest if the bijection ${\psi}$ (and ${\psi}^{-1}$) can be computed by low-level circuits.

\[prop:TC0\] The bijections ${\psi}$ and ${\psi}^{-1}$ are computable in DLOGTIME-uniform ${\mathbf{TC^{0}}}$.

In fact, we show that for all $i \in [n+1]$ there is an ${\mathbf{NC^{0}}}$-reduction from ${{\sf majority}}$ to ${\psi}_i$. That is, ${\mathbf{TC^{0}}}$ is the “correct” complexity of ${\psi}$, and in particular, ${\psi}$ is not in ${\mathbf{AC^{0}}}$. See Proposition \[prop:maj leq f\_1\] and Remark \[rem:maj leq f\_i\] for details.

The Complexity of Distributions {#sec:motivation}
-------------------------------

Lower bounds in circuit complexity are usually concerned with showing that a family of functions $\{f_n \colon {\{0,1\}^{n}}\to \{0,1\}\}_{n \in {{\mathbb N}}}$ cannot be computed by a family of circuits $\{C_n\}_{n \in {{\mathbb N}}}$ belonging to some natural class of circuits such as ${\mathbf{AC^{0}}}$ or ${\mathbf{TC^{0}}}$. Taking a broader interpretation of computation, it is often interesting to show that a 