ECCC-Report TR04-088https://eccc.weizmann.ac.il/report/2004/088Comments and Revisions published for TR04-088en-usFri, 22 Oct 2004 16:57:11 +0200
Paper TR04-088
| Fooling Parity Tests with Parity Gates |
Emanuele Viola,
Dan Gutfreund
https://eccc.weizmann.ac.il/report/2004/088We study the complexity of computing $k$-wise independent and
$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.
Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.
given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.
Mansour, Nisan and Tiwari (1990) show that constant depth circuits of size poly(n) (i.e. $AC^0$) cannot explicitly compute
$k$-wise independent and $\epsilon$-biased generators with seed length $n = 2^{\log^{o(1)} m}$.
In this work we show that DLOGTIME-uniform constant depth circuits
of size poly(n) \emph{with parity gates} can explicitly compute
$k$-wise independent and $\eps$-biased generators with seed length $n = (\poly) \log m$.
In some cases the seed length of our generators is optimal up to constant factors, and in general up to polynomial factors.
To obtain our results, we show a new construction of combinatorial designs, and we also show how to compute, in DLOGTIME-uniform $AC^0$, random walks
of length $log^c n$ over certain expander graphs of size $2^n$.
Fri, 22 Oct 2004 16:57:11 +0200https://eccc.weizmann.ac.il/report/2004/088