Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR14-057 | 9th July 2016 07:15

#### Dimension, Pseudorandomness and Extraction of Pseudorandomness

Revision #3
Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Accepted on: 9th July 2016 07:15
Keywords:

Abstract:

In this paper we propose a quantification of ensemble of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on an ensemble of distributions is quantitatively equivalent to the notion of \emph{dimension} we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy.

Further, we apply our quantification to the following problem. If we know that the dimension of an ensemble of distributions on the set of $n$-length strings is $s \in (0,1]$, can we extract out $O(sn)$ pseudorandom bits out of the distribution? We show that to construct such extractor, one needs at least $\Omega(\log n)$ bits of pure randomness. However, it is still open to do the same using $O(\log n)$ random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor \emph{et al.}, which we term \emph{nonpseudorandom bit-fixing source}. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic \emph{pseudorandom extractor} for this source.

By the end, we make a little progress towards {\P} vs. {\BPP} problem by showing that existence of optimal stretching function that stretches $O(\log n)$ input bits to produce $n$ output bits such that output distribution has dimension $s \in (0,1]$, implies {\P}={\BPP}.

Changes to previous version:

The main change is that in the revised paper we focus on ensemble of distributions rather than on single distributions. Also some technical details in some of the proofs were missing in the earlier version.

Revision #2 to TR14-057 | 9th July 2016 07:12

#### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revision #2
Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Accepted on: 9th July 2016 07:12
Keywords:

Abstract:

In this paper we propose a quantification of ensemble of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on an ensemble of distributions is quantitatively equivalent to the notion of \emph{dimension} we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy.

Further, we apply our quantification to the following problem. If we know that the dimension of an ensemble of distributions on the set of $n$-length strings is $s \in (0,1]$, can we extract out $O(sn)$ pseudorandom bits out of the distribution? We show that to construct such extractor, one needs at least $\Omega(\log n)$ bits of pure randomness. However, it is still open to do the same using $O(\log n)$ random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor \emph{et al.}, which we term \emph{nonpseudorandom bit-fixing source}. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic \emph{pseudorandom extractor} for this source.

By the end, we make a little progress towards {\P} vs. {\BPP} problem by showing that existence of optimal stretching function that stretches $O(\log n)$ input bits to produce $n$ output bits such that output distribution has dimension $s \in (0,1]$, implies {\P}={\BPP}.

Changes to previous version:

The main change is that in the revised paper we focus on ensemble of distributions rather than on single distributions. Also some technical details in some of the proofs were missing in the earlier version.

Revision #1 to TR14-057 | 13th October 2015 11:14

#### Dimension, Pseudorandomness and Extraction of Pseudorandomness

Revision #1
Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Accepted on: 13th October 2015 11:14
Keywords:

Abstract:

In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of \emph{dimension} we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy.

Further, we apply our quantification to the following problem. If we know that the dimension of a distribution on the set of $n$-length strings is $s \in (0,1]$, can we extract out $O(sn)$ pseudorandom bits out of the distribution? We show that to construct such extractor, one need at least $\Omega(\log n)$ bits of pure randomness. However, it is still open to do the same using $O(\log n)$ random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor \emph{et al.}, which we term \emph{nonpseudorandom bit-fixing source}. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic \emph{pseudorandom extractor} for this source.

By the end, we make a little progress towards {\P} vs. {\BPP} problem by showing that existence of optimal stretching function that stretches $O(\log n)$ input bits to produce $n$ output bits such that output distribution has dimension $s \in (0,1]$, implies {\P}={\BPP}.

Changes to previous version:

definition of win of an s-gale is different, several proofs have been modified and a few new results on pseudoentropy has been added

### Paper:

TR14-057 | 17th April 2014 20:23

#### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

TR14-057
Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Publication: 18th April 2014 23:49
Keywords:

Abstract:

In this paper, we propose a quantification of distributions on a set
of strings, in terms of how close to pseudorandom the distribution
is. The quantification is an adaptation of the theory of dimension of
sets of infinite sequences first introduced by Lutz
\cite{Lutz:DISS}.
We show that this definition is robust, by considering an alternate, equivalent
quantification. It is known that pseudorandomness can be characterized
in terms of predictors \cite{Yao82a}. Adapting Hitchcock
\cite{Hitchcock:FDLLU}, we show that the log-loss function incurred by
a predictor on a distribution is quantitatively equivalent to the
notion of dimension we define. We show that every distribution on a
set of strings of length $n$ has a dimension $s\in[0,1]$, and for
every $s \in [0,1]$ there is a distribution with dimension $s$. We
study some natural properties of our notion of dimension.
Further, we propose an application of our quantification to the
following problem. If we know that the dimension of a distribution on
the set of $n$-length strings is $s \in [0,1]$, can we
deterministically extract out $sn$ \emph{pseudorandom} bits out of the
distribution? We show that this is possible in a special case - a
notion analogous to the bit-fixing sources introduced by Chor
\emph{et. al.} \cite{CGHFRS85}, which we term a \emph{nonpseudorandom
bit-fixing source}. We adapt the techniques of Kamp and Zuckerman
\cite{KZ03} and Gabizon, Raz and Shaltiel \cite{GRS05} to establish
that in the case of a non-pseudorandom bit-fixing source, we can
deterministically extract the pseudorandom part of the
source. Further, we show that the existence of optimal nonpseudorandom
generator is enough to show ${\P}={\BPP}$.

ISSN 1433-8092 | Imprint