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}.
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.
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}.
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.
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}.
definition of win of an s-gale is different, several proofs have been modified and a few new results on pseudoentropy has been added
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}$.
