ECCC-Report TR16-018https://eccc.weizmann.ac.il/report/2016/018Comments and Revisions published for TR16-018en-usSat, 09 Jun 2018 04:16:06 +0300
Revision 7
| Randomness Extraction in $AC^0$ and with Small Locality |
Kuan Cheng,
Xin Li
https://eccc.weizmann.ac.il/report/2016/018#revision7Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice.\ While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than $\mathsf{P}$.
In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits ($AC^0$), and (2) the local computation model. Previous work in these models, such as [Vio05a], [GVW15] and [BG13], only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. Our results on $AC^0$ extractors refute a conjecture in [GVW15] and answer several open problems there. We also provide a lower bound on the error of extractors in $AC^0$, which together with the entropy lower bound in [Vio05a, GVW15] almost completely characterizes extractors in this class. Our results on local extractors also significantly improve the seed length in [BG13]. As an application, we use our $AC^0$ extractors to study pseudorandom generators in $AC^0$, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters.
Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the $AC^0$ property and small locality, and (2) a seeded randomness condenser with small locality.Sat, 09 Jun 2018 04:16:06 +0300https://eccc.weizmann.ac.il/report/2016/018#revision7
Revision 6
| Randomness Extraction in $\mathsf{AC}^0$ and with Small Locality |
Kuan Cheng,
Xin Li
https://eccc.weizmann.ac.il/report/2016/018#revision6Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than $\mathsf{P}$.
In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits ($\mathsf{AC}^0$), and (2) the local computation model. Previous work in these models, such as as [Vio05a], [GVW15] and [BG13], only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. Our results on $\mathsf{AC}^0$ extractors refute a conjecture in [GVW15] and answer several open problems there. We also provide a lower bound on the error of extractors in $\mathsf{AC}^0$, which together with the entropy lower bound in [Vio05a, GVW15] almost completely characterizes extractors in this class. Our results on local extractors also significantly improve the seed length in [BG13]. As an application, we use our $\mathsf{AC}^0$ extractors to study pseudorandom generators in $\mathsf{AC}^0$, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters.
Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the $\mathsf{AC}^0$ property and small locality, and (2) a seeded randomness condenser with small locality.Sat, 09 Jun 2018 04:09:36 +0300https://eccc.weizmann.ac.il/report/2016/018#revision6
Revision 5
| Randomness Extraction in $AC^0$ and with Small Locality |
Xin Li,
Kuan Cheng
https://eccc.weizmann.ac.il/report/2016/018#revision5Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice.\ While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than $\mathsf{P}$.
In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits ($\AC^0$), and (2) the local computation model. Previous work in these models, such as \cite{viola2005complexity}, \cite{goldreich2015randomness} and \cite{bogdanov2013sparse}, only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. Our results on $\AC^0$ extractors refute a conjecture in \cite{goldreich2015randomness} and answer several open problems there. We also provide a lower bound on the error of extractors in $\AC^0$, which together with the entropy lower bound in \cite{viola2005complexity, goldreich2015randomness} almost completely characterizes extractors in this class. Our results on local extractors also significantly improve the seed length in \cite{bogdanov2013sparse}. As an application, we use our $\AC^0$ extractors to study pseudorandom generators in $\AC^0$, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters.
Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the $\AC^0$ property and small locality, and (2) a seeded randomness condenser with small locality.Wed, 24 Jan 2018 19:08:52 +0200https://eccc.weizmann.ac.il/report/2016/018#revision5
Revision 4
| Randomness Extraction in $AC^0$ and with Small Locality |
Xin Li,
Kuan Cheng
https://eccc.weizmann.ac.il/report/2016/018#revision4Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice.\ While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than $\mathsf{P}$.
In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits ($\AC^0$), and (2) the local computation model. Previous work in these models, such as \cite{goldreich2015randomness} and \cite{bogdanov2013sparse}, only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. Our results on $\AC^0$ extractors refute a conjecture in \cite{goldreich2015randomness} and answer several open problems there. We also provide a lower bound on the error of extractors in $\AC^0$, which together with the entropy lower bound in \cite{goldreich2015randomness} almost completely characterizes extractors in this class. Our results on local extractors also significantly improve the seed length in \cite{bogdanov2013sparse}. As an application, we use our $\AC^0$ extractors to study pseudorandom generators in $\AC^0$, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters.
Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the $\AC^0$ property and small locality, and (2) a seeded randomness condenser with small locality.Tue, 23 Jan 2018 17:40:04 +0200https://eccc.weizmann.ac.il/report/2016/018#revision4
Revision 3
| Randomness Extraction in $AC^0$ and with Small Locality |
Xin Li,
Kuan Cheng
https://eccc.weizmann.ac.il/report/2016/018#revision3We 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)$.Sat, 12 Nov 2016 05:21:41 +0200https://eccc.weizmann.ac.il/report/2016/018#revision3
Revision 2
| Randomness Extraction in $AC^0$ and with Small Locality |
Xin Li,
Kuan Cheng
https://eccc.weizmann.ac.il/report/2016/018#revision2We 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)$.
Sat, 12 Nov 2016 05:06:03 +0200https://eccc.weizmann.ac.il/report/2016/018#revision2
Revision 1
| Randomness Extraction in $AC^0$ and with Small Locality |
Kuan Cheng,
Xin Li
https://eccc.weizmann.ac.il/report/2016/018#revision1We 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)$.
Fri, 19 Feb 2016 17:15:32 +0200https://eccc.weizmann.ac.il/report/2016/018#revision1
Paper TR16-018
| Randomness Extraction in $AC^0$ and with Small Locality |
Xin Li,
Kuan Cheng
https://eccc.weizmann.ac.il/report/2016/018We 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)$.
Fri, 05 Feb 2016 16:36:03 +0200https://eccc.weizmann.ac.il/report/2016/018