ECCC-Report TR09-114https://eccc.weizmann.ac.il/report/2009/114Comments and Revisions published for TR09-114en-usFri, 13 Nov 2009 16:42:24 +0200
Paper TR09-114
| Are all distributions easy? |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2009/114Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.
Our main results are:
\begin{itemize}
\item There are explicit $AC^0$ circuits of size poly(n) and depth $O(1)$ whose output distribution has statistical distance $1/2^n$ from the distribution $(X,\sum_i X_i) \in \{0,1\}^{n} \times \set{0,1,\ldots,n}$ for uniform $X \in \{0,1\}^n$, despite the inability of these circuits to compute $\sum_i x_i$ given $x$.
Previous examples of this phenomenon apply to different distributions such as $(X, \sum_i X_i \mod 2) \in \{0,1\}^{n+1}$.
We also prove a lower bound independent from $n$ on the statistical distance between the output distribution of $NC^0$ circuits and the distribution $(X,\maj(X))$. We show that $1-o(1)$ lower bounds for related distributions yield lower bounds for succinct data structures.
\item Uniform randomized $AC^0$ circuits of poly(n) size and depth $d = O(1)$ with error $\epsilon$ can be simulated by uniform randomized circuits of poly(n) size and depth $d+1$ with error $\epsilon + o(1)$ using $\le (\log n)^{O( \log \log n)}$ random bits.
Previous derandomizations [Ajtai and Wigderson '85; Nisan '91] increase the depth by a constant factor, or else have poor seed length.
\end{itemize}
Given the right tools, the above results have technically simple proofs.
Fri, 13 Nov 2009 16:42:24 +0200https://eccc.weizmann.ac.il/report/2009/114