Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR16-018 | 12th November 2016 05:21

#### Randomness Extraction in $AC^0$ and with Small Locality

Revision #3
Authors: Kuan Cheng, Xin Li
Accepted on: 12th November 2016 05:21
Keywords:

Abstract:

We study two variants of randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is extractors that can be computed by $\AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that have a small number of overall input-output dependencies (called \emph{sparse extractor families}). In this paper we focus on the stronger condition where any function in the family can be computed by local functions. The parameters here are the length of the source $n$, the min-entropy $k=k(n)$, the seed length $d=d(n)$, the output length $m=m(n)$, the error $\eps=\eps(n)$, and the locality of functions $\ell=\ell(n)$.

In the $\AC^0$ extractor case, we study both seeded extractors and deterministic extractors for bit-fixing sources. Our negative results show that the error of such extractors cannot be better than $2^{-\poly(\log n)}$. Together with the lower bound on entropy in \cite{goldreich2015randomness} this almost completely characterizes the power of $\AC^0$ extractors. Our positive results substantially improve the positive results in \cite{goldreich2015randomness}, where for weak sources with $k \geq n/\poly(\log n)$ a seed length of $O(m)$ is required to extract $m$ bits with error $1/\poly(n)$. We give constructions of strong seeded extractors for $k \geq n/\poly(\log n)$, with seed length $d=O(\log n)$, output length $m=(1-\gamma)k$ for any constant $0<\gamma<1$, and error any $1/\poly(n)$. In addition, we can reduce the error to $2^{-\poly(\log n)}$ at the price of increasing the seed length to $d=\poly(\log n)$, essentially matching our error bound. We give two applications of such extractors to the constructions of pseudorandom generators in $\AC^0$ that are cryptographically secure, and that fool small space computation. In addition, we give the first \emph{explicit} $\AC^0$ extractor for oblivious bit-fixing sources with entropy $k \geq n/\poly(\log n)$, output length $m=(1-\gamma)k$ and error $2^{-\poly(\log n)}$, which are essentially optimal.

In the case of sparse extractor families, Bogdanov and Guo \cite{bogdanov2013sparse} gave constructions for any min-entropy $k$ with locality at least $O(n/k\log (m/\eps)\log (n/m))$, but the family size is quite large, i.e., $2^{nm}$. Equivalently, this means the seed length is at least $nm$. In this paper we significantly reduce the seed length. For $k \geq n/\poly(\log n)$ and $\eps \geq 2^{-k^{\Omega(1)}}$, we show how to get a strong seeded extractor with seed length $d =O(\log n + \frac{\log^2(1/\epsilon)}{\log n})$, output length $m = k^{\Omega(1)}$ and locality $\log^2 (1/\epsilon) \poly(\log n)$. In addition, for min-entropy $k=\Omega(\log^2 n)$ and error $\eps \geq 2^{-k^{\Omega(1)}}$, we give a strong seeded extractor with seed length $d = O(k)$, $m = (1-\gamma)k$ and locality $\frac{n}{k}\log^2 (1/\epsilon) (\log n)\poly(\log k)$. As an intermediate tool for this extractor, we construct a condenser that condenses an $(n, k)$-source into a $(10k, \Omega(k))$-source with seed length $d=O(k)$, error $2^{-\Omega(k)}$ and locality $\Theta(\frac{n}{k}\log n)$.

Changes to previous version:

Negative results for errors of AC^0 extractors are added. The construction of deterministic AC^0 extractors for bit-fixing sources is given.

Revision #2 to TR16-018 | 12th November 2016 05:06

#### Randomness Extraction in $AC^0$ and with Small Locality

Revision #2
Authors: Kuan Cheng, Xin Li
Accepted on: 12th November 2016 05:06
Keywords:

Abstract:

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that have a small number of overall input-output dependencies (called \emph{sparse extractor families}). In this paper we focus on the stronger condition where any function in the family can be computed by local functions. The parameters here are the length of the source $n$, the min-entropy $k=k(n)$, the seed length $d=d(n)$, the output length $m=m(n)$, the error $\epsilon=\epsilon(n)$, and the locality of functions $\ell=\ell(n)$.

In the $AC^0$ extractor case, our main results substantially improve the positive results in \cite{goldreich2015randomness}, where for $k \geq n/\poly(\log n)$ a seed length of $O(m)$ is required to extract $m$ bits with error $1/\poly(n)$. We give constructions of strong seeded extractors for $k=\delta n \geq n/\poly(\log n)$, with seed length $d=O(\log n)$, output length $m=k^{\Omega(1)}$, and error any $1/\poly(n)$. We can then boost the output length to $\Omega(\delta k)$ with seed length $d=O(\log n)$, or to $(1-\gamma)k$ for any constant $0<\gamma<1$ with $d=O(\frac{1}{\delta}\log n)$. In the special case where $\delta$ is a constant and $\epsilon=1/\poly(n)$, our parameters are essentially optimal. In addition, we can reduce the error to $2^{-\poly(\log n)}$ at the price of increasing the seed length to $d=\poly(\log n)$.

In the case of sparse extractor families, Bogdanov and Guo \cite{bogdanov2013sparse} gave constructions for any min-entropy $k$ with locality at least $O(n/k\log (m/\epsilon)\log (n/m))$, but the family size is quite large, i.e., $2^{nm}$. Equivalently, this means the seed length is at least $nm$. In this paper we significantly reduce the seed length. For $k \geq n/\poly(\log n)$ and error $1/\poly(n)$, our $AC^0$ extractor with output $k^{\Omega(1)}$ also has small locality $\ell=\poly(\log n)$, and the seed length is only $O(\log n)$. We then show that for $k \geq n/\poly(\log n)$ and $\epsilon \geq 2^{-k^{\Omega(1)}}$, we can use our error reduction techniques to get a strong seeded extractor with seed length $d =O(\log n + \frac{\log^2(1/\epsilon)}{\log n})$, output length $m = k^{\Omega(1)}$ and locality $\log^2 (1/\epsilon) \poly(\log n)$. Finally, for min-entropy $k=\Omega(\log^2 n)$ and error $\epsilon \geq 2^{-k^{\Omega(1)}}$, we give a strong seeded extractor with seed length $d = O(k)$, $m = (1-\gamma)k$ and locality $\frac{n}{k}\log^2 (1/\epsilon) (\log n)\poly(\log k)$. As an intermediate tool for this extractor, we construct a condenser that condenses an $(n, k)$-source into a $(10k, \Omega(k))$-source with seed length $d=O(k)$, error $2^{-\Omega(k)}$ and locality $\Theta(\frac{n}{k}\log n)$.

Revision #1 to TR16-018 | 19th February 2016 17:15

#### Randomness Extraction in $AC^0$ and with Small Locality

Revision #1
Authors: Kuan Cheng, Xin Li
Accepted on: 19th February 2016 17:15
Keywords:

Abstract:

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that have a small number of overall input-output dependencies (called \emph{sparse extractor families}). In this paper we focus on the stronger condition where any function in the family can be computed by local functions. The parameters here are the length of the source $n$, the min-entropy $k=k(n)$, the seed length $d=d(n)$, the output length $m=m(n)$, the error $\epsilon=\epsilon(n)$, and the locality of functions $\ell=\ell(n)$.

In the $AC^0$ extractor case, our main results substantially improve the positive results in \cite{goldreich2015randomness}, where for $k \geq n/\poly(\log n)$ a seed length of $O(m)$ is required to extract $m$ bits with error $1/\poly(n)$. We give constructions of strong seeded extractors for $k=\delta n \geq n/\poly(\log n)$, with seed length $d=O(\log n)$, output length $m=k^{\Omega(1)}$, and error any $1/\poly(n)$. We can then boost the output length to $\Omega(\delta k)$ with seed length $d=O(\log n)$, or to $(1-\gamma)k$ for any constant $0<\gamma<1$ with $d=O(\frac{1}{\delta}\log n)$. In the special case where $\delta$ is a constant and $\epsilon=1/\poly(n)$, our parameters are essentially optimal. In addition, we can reduce the error to $2^{-\poly(\log n)}$ at the price of increasing the seed length to $d=\poly(\log n)$.

In the case of sparse extractor families, Bogdanov and Guo \cite{bogdanov2013sparse} gave constructions for any min-entropy $k$ with locality at least $O(n/k\log (m/\epsilon)\log (n/m))$, but the family size is quite large, i.e., $2^{nm}$. Equivalently, this means the seed length is at least $nm$. In this paper we significantly reduce the seed length. For $k \geq n/\poly(\log n)$ and error $1/\poly(n)$, our $AC^0$ extractor with output $k^{\Omega(1)}$ also has small locality $\ell=\poly(\log n)$, and the seed length is only $O(\log n)$. We then show that for $k \geq n/\poly(\log n)$ and $\epsilon \geq 2^{-k^{\Omega(1)}}$, we can use our error reduction techniques to get a strong seeded extractor with seed length $d =O(\log n + \frac{\log^2(1/\epsilon)}{\log n})$, output length $m = k^{\Omega(1)}$ and locality $\log^2 (1/\epsilon) \poly(\log n)$. Finally, for min-entropy $k=\Omega(\log^2 n)$ and error $\epsilon \geq 2^{-k^{\Omega(1)}}$, we give a strong seeded extractor with seed length $d = O(k)$, $m = (1-\gamma)k$ and locality $\frac{n}{k}\log^2 (1/\epsilon) (\log n)\poly(\log k)$. As an intermediate tool for this extractor, we construct a condenser that condenses an $(n, k)$-source into a $(10k, \Omega(k))$-source with seed length $d=O(k)$, error $2^{-\Omega(k)}$ and locality $\Theta(\frac{n}{k}\log n)$.

Changes to previous version:

Corrected some typos and minor mistakes, added some details in appendix

### Paper:

TR16-018 | 3rd February 2016 21:50

#### Randomness Extraction in $AC^0$ and with Small Locality

TR16-018
Authors: Kuan Cheng, Xin Li
Publication: 5th February 2016 16:36
Keywords:

Abstract:

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that have a small number of overall input-output dependencies (called \emph{sparse extractor families}). In this paper we focus on the stronger condition where any function in the family can be computed by local functions. The parameters here are the length of the source $n$, the min-entropy $k=k(n)$, the seed length $d=d(n)$, the output length $m=m(n)$, the error $\epsilon=\epsilon(n)$, and the locality of functions $\ell=\ell(n)$.

In the $AC^0$ extractor case, our main results substantially improve the positive results in \cite{goldreich2015randomness}, where for $k \geq n/\poly(\log n)$ a seed length of $O(m)$ is required to extract $m$ bits with error $1/\poly(n)$. We give constructions of strong seeded extractors for $k=\delta n \geq n/\poly(\log n)$, with seed length $d=O(\log n)$, output length $m=k^{\Omega(1)}$, and error any $1/\poly(n)$. We can then boost the output length to $\Omega(\delta k)$ with seed length $d=O(\log n)$, or to $(1-\gamma)k$ for any constant $0<\gamma<1$ with $d=O(\frac{1}{\delta}\log n)$. In the special case where $\delta$ is a constant and $\epsilon=1/\poly(n)$, our parameters are essentially optimal. In addition, we can reduce the error to $2^{-\poly(\log n)}$ at the price of increasing the seed length to $d=\poly(\log n)$.

In the case of sparse extractor families, Bogdanov and Guo \cite{bogdanov2013sparse} gave constructions for any min-entropy $k$ with locality at least $O(n/k\log (m/\epsilon)\log (n/m))$, but the family size is quite large, i.e., $2^{nm}$. Equivalently, this means the seed length is at least $nm$. In this paper we significantly reduce the seed length. For $k \geq n/\poly(\log n)$ and error $1/\poly(n)$, our $AC^0$ extractor with output $k^{\Omega(1)}$ also has small locality $\ell=\poly(\log n)$, and the seed length is only $O(\log n)$. We then show that for $k \geq n/\poly(\log n)$ and $\epsilon \geq 2^{-k^{\Omega(1)}}$, we can use our error reduction techniques to get a strong seeded extractor with seed length $d =O(\log n + \frac{\log^2(1/\epsilon)}{\log n})$, output length $m = k^{\Omega(1)}$ and locality $\log^2 (1/\epsilon) \poly(\log n)$. Finally, for min-entropy $k=\Omega(\log^2 n)$ and error $\epsilon \geq 2^{-k^{\Omega(1)}}$, we give a strong seeded extractor with seed length $d = O(k)$, $m = (1-\gamma)k$ and locality $\frac{n}{k}\log^2 (1/\epsilon) (\log n)\poly(\log k)$. As an intermediate tool for this extractor, we construct a condenser that condenses an $(n, k)$-source into a $(10k, \Omega(k))$-source with seed length $d=O(k)$, error $2^{-\Omega(k)}$ and locality $\Theta(\frac{n}{k}\log n)$.

ISSN 1433-8092 | Imprint