Dimension,pseudorandomness and extraction of pseudorandomness 1

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 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 (s n)$ pseudorandom bits out of the distribution? We show that to construct such extractor, one needs at least $Ω (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 et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic 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$ .

Keywords

Pseudorandomness dimension unpredictability pseudoentropy pseudorandom extractor

1. Introduction

Incorporating randomness in a feasible computation is one of the basic primitives in theoretical computer science. Fortunately, any efficient (polynomial time) randomized algorithm does not require pure random bits. What it actually needs is a source that looks random to it and this is where the notion of pseudorandomness [5,35] comes into picture. Since its introduction, pseudorandomness has been fundamental to the domain of cryptography, complexity theory and computational learning theory. Pseudorandomness is mainly a computational approach to study the nature of randomness, and computational indistinguishability [11] played a pivotal role in this. Informally, a distribution is said to be pseudorandom if no efficient algorithm can distinguish it from the uniform distribution. Another way of looking at computational indistinguishability is via the notion of unpredictability of distributions, due to Yao [35]. Informally, a distribution is unpredictable if there is no efficient algorithm that, given a prefix of a string coming from that distribution, can guess the next bit with a significant success probability. This line of research naturally posed the question of constructing algorithms that can generate pseudorandom distributions, known as pseudorandom generators. Till now we know such constructions by assuming the existence of one-way functions. It is well known that constructibility of an optimal pseudorandom generator implies complete derandomization (i.e., $P = BPP$ ) and exponential hardness assumption on one-way function enables us to do that. However, Nisan and Wigderson [26] showed that the existence of an exponential hard function, which is a much weaker assumption, is also sufficient for this purpose. The assumption was further weakened in [18].

In order to characterize the class of random sources, information theoretic notion of min-entropy is normally used. A computational analogue of entropy was introduced by Yao [35] and was based on compression. Håstad, Impagliazzo, Levin and Luby [13] extended the definition of min-entropy in computational settings while giving the construction of a pseudorandom generator from any one-way function. This HILL-type pseudoentropy basically extends the definition of pseudorandomness syntactically. Relations among above two types of pseudoentropy was further studied in [4]. A more relaxed notion of pseudoentropy, known as next-bit Shannon pseudoentropy, was later introduced by Haitner, Reingold and Vadhan [12] in the context of an efficient construction of a pseudorandom generator from any one-way function. In a follow up work [33], the same notion was alternatively characterized by KL-hardness. So far it is not clear which of the above notions is the most appropriate or whether they are at all suitable to characterize distributions in terms of the degree of pseudorandomness in it.

In this paper, we first propose an alternative measure to quantify the amount of pseudorandomness present in a distribution. This measure is motivated by the ideas of dimension [23] and logarithmic loss unpredictability [14]. Lutz used the betting functions known as gales to characterize the Hausdroff dimension of sets of infinite sequences over a finite alphabet. The definition given by Lutz cannot be carried over directly, because here we consider the distributions over finite length strings instead of sets containing infinite length strings. To overcome this difficulty, we allow “non-uniform” gales and introduce a new probabilistic notion of success of a gale over a distribution. We use this to define two notions of dimension of a distribution – strong one and a weak one. Both the notions were already there for the case of infinite strings [24]. In [14], Hitchcock showed that the definition of dimension given by Lutz is equivalent to logarithmic loss unpredictability. In this paper, we show that this result can be adapted to establish a quantitative equivalence between the notion of logarithmic loss unpredictability of a distribution and our proposed notion of dimension. Roughly, this captures the essence of equivalence between pseudorandomness defined via indistinguishability and via unpredictability [35]. We show some important properties of the notion of dimension of a distribution, which eventually makes this characterization much more powerful and flexible. We also do a comparative study between our notion of dimension and two known notions of pseudoentropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. We show that the class of distributions with high dimension is a strict superset of the class of distributions having high HILL-type pseudo min-entropy. Whereas, there is a much closer relationship between dimension and next-bit pseudo Shannon entropy.

Once we have a quantification of pseudorandomness of a distribution, the next natural question is how to extract the pseudorandom part from a given distribution. The question is similar to the question of constructing randomness extractors which is an efficient algorithm that converts a realistic source to an almost ideal source of randomness. The term randomness extractor was first defined by Nisan and Zuckerman [27]. Unfortunately there is no such deterministic algorithm and to extract out almost all the randomness, extra $Ω (log n)$ pure random bits are always required [28,30]. There is a long line of research on construction of extractors towards achieving this bound. For a comprehensive treatment on this topic, we refer the reader to excellent surveys by Nisan and Ta-Shma [25] and Shaltiel [31]. Finally, the desired bound was achieved up to some constant factor in [20].

Coming back to the computational analogue, it is natural to study the same question in the domain of pseudorandomness. Given a distribution with dimension s, the problem is to output $O (s n)$ many bits that are pseudorandom. A simple argument can show that deterministic pseudorandom extraction is not possible, but it is not at all clear that how many pure random bits are necessary to serve the purpose. In this paper, we show that we need to actually involve $Ω (log n)$ random bits to extract out all the pseudorandomness present in a distribution. However explicit construction of one such extractor with $O (log n)$ random bits is not known. If it is known that the given distribution has high HILL-type pseudo min-entropy, then any randomness extractor will work [4]. Instead of HILL-type pseudoentropy, even if we have Yao-type pseudo min-entropy, then also some special kind of randomness extractor (namely with a “reconstruction procedure”) could serve our purpose [4]. Unfortunately both of these notions of pseudoentropy can be very small for a distribution with very high dimension. Actually the same counterexample will work for both cases. So it is interesting to come up with an pseudorandom extractor for a class of distributions having high dimension.

As a first step towards this goal, we consider a special kind of source which we call the nonpseudorandom bit-fixing source. It is similar to the well studied notion of bit-fixing random source introduced by Chor et al. [6], for which we know the construction of a deterministic randomness extractor due to [19] and [9]. In this paper, we show that the same construction yields a deterministic pseudorandom extractor for all nonpseudorandom bit-fixing sources having polynomial-size support.

In the concluding section, we make a little progress towards the question of P vs. $BPP$ by showing that in order to prove $P = BPP$ , it is sufficient to construct an algorithm that stretches $O (log n)$ pure random bits to n bits such that the output distribution has a non-zero weak dimension (not necessarily pseudorandom). The idea is that using such stretching algorithm, we easily construct a hard function, which eventually gives us the most desired optimal pseudorandom generator.

Notations.
In this paper, we consider the binary alphabet $Σ = {0, 1}$ . We denote $\Pr_{x \in_{R} D} [E]$ as $D [E]$ , where E is an event and x is drawn randomly according to the distribution D. We use $U_{m}$ to denote the uniform distribution on $Σ^{m}$ . Given a string $x \in Σ^{n}$ , $x [i]$ denote the ith bit of x and $x [1, \dots, i]$ denotes the first i bits of x. Now suppose $x \in Σ^{n}$ and $S = {s_{1}, s_{2}, \dots, s_{k}} \subseteq {1, 2, \dots, n}$ , then by $x_{S}$ , we denote the string $x [s_{1}] x [s_{2}] \dots x [s_{k}]$ .

2. Quantification of pseudorandomness

In this section, we propose a quantification of pseudorandomness present in a distribution. We adapt the notion introduced by Lutz [23] of an s-gale to define a variant notion of success of an s-gale against a distribution D on $Σ^{n}$ . Throughout this paper, we will talk about non-uniform definitions. First, we consider the definition of pseudorandomness.

2.1. Pseudorandomness

We start by defining the notion of indistinguishability which we will use frequently in this paper.

Definition 2.1 (Indistinguishability).

A distribution D over $Σ^{n}$ is $(S, ε)$ -indistinguishable from another distribution $D^{'}$ over $Σ^{n}$ (for $S \in N, ε > 0$ ) if for every circuit C of size at most S, $\begin{matrix} | D [C (x) = 1] - D^{'} [C (x) = 1] | ⩽ ε . \end{matrix}$

Now we are ready to introduce the notion of pseudorandomness.

Definition 2.2 (Pseudorandomness).

For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ ,2

²
Throughout this paper, we consider $S (n) > n$ so that the circuit can at least read the full input.

ε = ε (n) > 0

(via computational indistinguishability) D is said to be $(S, ε)$ -pseudorandom if for all sufficiently large n, $D_{n}$ is $(O (S (n)), ε (n))$ -indistinguishable from $U_{n}$ ; or equivalently,

(via unpredictability [35]) D is said to be $(S, ε)$ -pseudorandom if for all sufficiently large n, $\begin{matrix} D_{n} [C (x_{1}, \dots, x_{i - 1}) = x_{i}] ⩽ \frac{1}{2} + \frac{ε (n)}{n} \end{matrix}$ for all circuits C of size at most $O (S (n))$ and for all $i \in [n]$ .

It is always natural to consider asymptotic definitions with respect to all polynomial size circuits and allowing bias term to be any inverse polynomial. An ensemble of distributions $D = {D_{n}}_{n \in N}$ , where a distribution $D_{n}$ is on $Σ^{n}$ , is said to be pseudorandom if for every constant $c > 0$ and $c^{'} > 0$ , D is $(n^{c}, 1 / n^{c^{'}})$ -pseudorandom [10].

2.2. Martingales, s-gales and predictors

Martingales are “fair” betting games which are used extensively in probability theory (see for example, [3]). Lutz introduced a generalized notion, that of an s-gale, to characterize Hausdorff dimension [22] and Athreya et al. used a similar notion to characterize packing dimension [2].

Definition 2.3 ([22]).

Let $s \in [0, \infty)$ . An s-gale is a function $d : Σ^{*} \to [0, \infty)$ such that $d (λ) = 1$ and $d (w) = 2^{- s} [d (w 0) + d (w 1)]$ , $\forall w \in Σ^{*}$ . A martingale is a 1-gale.

The following proposition establishes a connection between s-gales and martingales.

Proposition 2.4 ([22]).

A function $d : Σ^{*} \to [0, \infty)$ is an s-gale if and only if the function $d^{'} : Σ^{*} \to [0, \infty)$ defined as $d^{'} (w) = 2^{(1 - s) | w |} d (w)$ is a martingale.

In order to adapt the notion of an s-gale to the study of pseudorandomness, we first relate it to the notion of predictors, which have been extensively used in the literature [33]. Given an initial finite segment of a string, a predictor specifies a probability distribution over Σ for the next symbol in the string.

Definition 2.5.
A function $π : Σ^{} \times Σ \to [0, 1]$ is a predictor* if for all $w \in Σ^{*}$ , $π (w, 0) + π (w, 1) = 1$ .

Note that the above definition of a predictor is not very different from the type of predictor used in Definition 2.2. If we have a predictor that given a prefix of a string outputs the next bit, then by invoking that predictor independently polynomially many times we can get an estimate on the probability of occurrence of 0 or 1 as the next bit. Using Chernoff bound it can easily be shown that the estimation is correct up to some inverse exponential error. For the detailed equivalence, the reader may refer to [33]. In this paper, we only consider the martingales (or s-gales) and predictors that can be computed using family of non-uniform circuits and from now onwards we refer to them just as martingales (or s-gales) and predictors, and by the size of a martingale (or an s-gale or a predictor), we refer the size of the circuit corresponding to that martingale (or s-gale or predictor).
2.3. Conversion between s-gale and predictor

There is an equivalence between an s-gale and a predictor. An early reference to this is [7]. We follow the construction given in [14].

A predictor π induces an s-gale $d_{π}$ for each $s \in [0, \infty)$ and is defined as follows: $d_{π} (λ) = 1$ , $d_{π} (w a) = 2^{s} d_{π} (w) π (w, a)$ for all $w \in Σ^{*}$ and $a \in Σ$ ; equivalently $d_{π} (w) = 2^{s | w |} \prod_{i = 1}^{| w |} π (w [1 \dots i - 1], w [i])$ for all $w \in Σ^{*}$ .

Conversely, an s-gale d with $d (λ) = 1$ induces a predictor $π_{d}$ defined as: if $d (w) \neq 0$ , $π_{d} (w, a) = 2^{- s} \frac{d (w a)}{d (w)}$ ; otherwise, $π_{d} (w, a) = \frac{1}{2}$ , for all $w \in Σ^{*}$ and $a \in Σ$ .

Hitherto, s-gales have been used to study the dimension of sets of infinite sequences – for an extensive bibliography, see [15] and [16]. Although in this paper, we consider distributions on finite length strings, the conversion procedure between s-gale and predictor will be exactly same as described above.

2.4. Defining dimension

Definition 2.6.
For any $ε > 0$ , an s-gale $d : Σ^{} \to [0, \infty)$ is said to ε-succeed over a distribution* $D_{n}$ on $Σ^{n}$ if $\begin{matrix} D_{n} [d (w) ⩾ 2] > \frac{1}{2} + ε . \end{matrix}$

Note that the above definition of win of an s-gale is not arbitrary and reader may refer to the last portion of the proof of Theorem 4.3 to get some intuition behind this definition. The following lemma states the equivalence between the standard definition of pseudorandomness and the definition using martingale.
Lemma 2.7.
Consider an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ . If D is $(S, ε)$ -pseudorandom then for all large enough n, there is no martingale of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}$ . Conversely, if for all large enough n, there is no martingale of size at most $O (S (n))$ that $\frac{ε (n)}{n}$ -succeeds on $D_{n}$ , then D is $(S, ε)$ -pseudorandom.
Proof.
Assume $d : Σ^{} \to [0, \infty)$ is a martingale which $ε (n)$ -succeeds on $D_{n}$ for some $n \in N$ , i.e., $\begin{matrix} D_{n} [d (w) ⩾ 2] > \frac{1}{2} + ε (n) . \end{matrix}$

By the Markov Inequality, $U_{n} [d (w) ⩾ 2] ⩽ \frac{1}{2}$ .

Let $C_{d}$ be a circuit of size $O (S (n))$ obtained by instantiating d at length n. Now let C be a circuit which outputs 1 if $C_{d} (w) ⩾ 2$ . Then, $\begin{matrix} | D_{n} [C (w) = 1] - U_{n} [C (w) = 1] | > ε (n) . \end{matrix}$

Thus D is not $(S, ε)$ -pseudorandom.

Now for the converse direction, assume that D is not $(S, ε)$ -pseudorandom. Then there exists an $n_{0} \in N$ such that for any $n ⩾ n_{0}$ there exists an bit position $i \in [0, n - 1)$ and some circuit C of size at most $O (S (n))$ for which $\begin{matrix} D_{n} [C (w_{1}, \dots, w_{i - 1}) = w_{i}] > \frac{1}{2} + \frac{ε (n)}{n} . \end{matrix}$

Now build a martingale $d : Σ^{} \to [0, \infty)$ using this circuit C as follows. Let $d (λ) = 1$ . Now, $\forall j \in [n], j \neq i$ , $d (w [0, \dots, j - 1] 0) = d (w [0, \dots, j - 1] 1) = d (w [0, \dots, j - 1])$ , and $d (w [0, \dots, i - 1] b) = 2 d (w [0, \dots, i - 1])$ , $d (w [0, \dots, i - 1] \overline{b}) = 0$ if $C (w [0, \dots, i - 1]) = b$ .

Now it is clear that $\begin{matrix} D_{n} [d (w) ⩾ 2] > \frac{1}{2} + \frac{ε (n)}{n} \end{matrix}$ and for all large enough n, the size of the martingale d is at most $O (S (n))$ . □

The next definition gives a complete quantification of distributions in terms of dimension.
Definition 2.8 (Weak dimension or dimension).

For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , the $(S, ε)$ -weak dimension or simply dimension of D is defined as $\begin{array}{rcl} {dim}_{S, ε} (D) & = & inf {s \in [0, \infty) | for infinitely many n, \exists s -gale d of size at most O (S (n)) which ε (n) -succeeds \\ on D_{n}} . \end{array}$

Informally, if the dimension of an ensemble of distribution is s, we say that it is s-pseudorandom. It is clear from Lemma 2.7 that for any $(S, ε)$ -pseudorandom ensemble of distributions D, ${dim}_{S, ε} (D) ⩾ 1$ . In Section 4 we will see that it is actually an equality. We can also define dimension of distributions in slightly stronger sense.

Definition 2.9 (Strong dimension).

For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , the $(S, ε)$ -strong dimension of D is defined as $\begin{array}{rcl} {sdim}_{S, ε} (D) & = & inf {s \in [0, \infty) | for all large enough n, \exists s -gale d of size at most O (S (n)) which ε (n) -succeeds \\ on D_{n}} . \end{array}$

It follows from the definition that weak dimension is smaller or equal to strong dimension.

Proposition 2.10.
For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , ${dim}_{S, ε} (D)$ and ${sdim}_{S, ε} (D)$ are well defined and $\begin{matrix} {dim}_{S, ε} (D) ⩽ {sdim}_{S, ε} (D) . \end{matrix}$

We will show separation between both of these notions of dimensions in Section 4. Now just like the asymptotic definition of pseudorandomness with respect to all polynomial size circuits and inverse polynomial bias, for any ensemble of distributions $D = {D_{n}}_{n \in N}$ , we can give definitions of weak dimension or simply dimension (denoted by $dim (D)$ ) and strong dimension (denoted by $sdim (D)$ ) by allowing $S (n)$ to be $n^{O (1)}$ and $ε (n)$ to be $n^{- O (1)}$ in the Definition 2.8 and 2.9 respectively.
3. Unpredictability and dimension

It is customary to measure the performance of a predictor utilizing a loss function [14]. The loss function determines the penalty incurred by a predictor for erring in its prediction. Let the next bit be b and the probability induced by the predictor on it is $p_{b}$ .

Commonly used loss functions include the absolute loss function, which penalizes the amount $1 - p_{b}$ ; and the logarithmic loss function, which penalizes $- log (p_{b})$ . The latter, which appears complicated at first glance, is intimately related to the concepts of Shannon Entropy and dimension. In this section, adapting the result of Hitchcock [14], we establish that there is an equivalence between the notion of dimension that we have defined in the previous section, and the logarithmic loss function defined on a predictor.

Definition 3.1.
The logarithmic loss function on $p \in [0, 1]$ is defined to be $loss (p) = - log p$ .

Using this, we define the running loss that a predictor incurs while it predicts successive bits of a string in $Σ^{n}$ , as the sum of the losses that the predictor makes on individual bits.
Definition 3.2.
Let $π : Σ^{} \times Σ \to [0, 1]$ be a predictor.
The cumulative loss* of π on $w \in Σ^{n}$ , denoted as $Loss (π, w)$ , is defined by $Loss (π, w) = \sum_{i = 1}^{n} loss (π (w [1, \dots, i - 1], w [i]))$ .

The loss rate of π on $w \in Σ^{n}$ is $LossRate (π, w) = \frac{Loss (π, w)}{n}$ .

The ε-loss rate of π over a distribution $D_{n}$ on $Σ^{n}$ is $\begin{matrix} {LossRate}_{ε} (π, D_{n}) = inf {t \in [0, 1] ∣ D_{n} [LossRate (π, w) ⩽ t] > \frac{1}{2} + ε} . \end{matrix}$

Intuitively the unpredictability of a distribution is defined as the infimum of the loss rate that any predictor has to incur on the distribution.
Definition 3.3 (Weak unpredictability or unpredictability).

For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , the $(S, ε)$ -weak unpredictability or simply unpredictability of D is $\begin{array}{l} {unpred}_{S, ε} (D) = & inf {t \in [0, 1] for infinitely many n, there exists a predictor π of size at most O (S (n)) \\ such that {LossRate}_{ε (n)} (π, D_{n}) ⩽ t} . \end{array}$

With this, we can prove that dimension can equivalently be defined using unpredictability. The proof is motivated from the proof of the equivalence between logarithmic loss unpredictability and dimension [14].

Theorem 3.4.
Consider any $s \in [0, 1]$ . For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , if ${dim}_{S, ε} (D) ⩽ s$ then ${unpred}_{S^{O (1)}, ε} (D) ⩽ s$ . Conversely, ${unpred}_{S, ε} (D) ⩽ s$ implies ${dim}_{S^{O (1)}, ε} (D) ⩽ s$ .
Proof.
Assume that $s^{'}$ is any number such that $s < s^{'}$ and then take a number $s^{″}$ such that $s < s^{″} ⩽ s^{'}$ and $2^{s^{″}}$ is rational.3
³
We consider $2^{s^{″}}$ to be rational to ensure that the value of $2^{s^{″}}$ can be computed using constant size circuit. Note that we can always find such $s^{″}$ due to the fact that the function $2^{s}$ for $s > 0$ is continuous, monotonically increasing and within any two real numbers there exists a rational number.

For some large enough n, suppose d is an $s^{″}$ -gale of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}$ . Let $π_{d} : Σ^{*} \times Σ \to [0, 1]$ be defined by $\begin{array}{l} π_{d} (w, b) & = \{\begin{matrix} 2^{- s^{″}} \frac{d (w b)}{d (w)} & if d (w) \neq 0, \\ \frac{1}{2} & otherwise . \end{matrix} \end{array}$

For any $w \in Σ^{n}$ with $d (w) ⩾ 2$ , we have $\begin{array}{l} {Loss}_{π_{d}} (w) & = - \sum_{i = 1}^{n} log π_{d} (w [1, \dots, i - 1], w [i]) \\ = - log \prod_{i = 1}^{n} π_{d} (w [1, \dots, i - 1], w [i]) \\ = s^{″} n - log d (w) \\ ⩽ s^{″} n - 1 ⩽ s^{'} n . \end{array}$ So $LossRate (π_{d}, w) ⩽ s^{'}$ . Thus, $\begin{array}{l} D_{n} [LossRate (π_{d}, w) ⩽ s^{'}] ⩾ D_{n} [d (w) ⩾ 2] > \frac{1}{2} + ε . \end{array}$ Note that implementation of $π_{d}$ involves division of two at most $O (S (n))$ bits rational numbers4
⁴
As we are considering martingales and predictors that can be implemented by circuits of size $O (S (n))$ so the output must be a rational number which can be represented by at most $O (S (n))$ bits.

and thus can be done using a circuit of size at most ${(S (n))}^{O (1)}$ [34].

Conversely, assume that ${unpred}_{S, ε} (D) ⩽ t \in [0, 1]$ . Assume that $t^{'}$ is any number satisfying $t < t^{'}$ and then take any number $t^{″}$ such that $t^{'} < t^{″}$ and $2^{t^{″}}$ is rational. For some large enough n, let π be a predictor of size at most $O (S (n))$ such that $\begin{matrix} D_{n} [LossRate (π, w) ⩽ t^{'}] > \frac{1}{2} + ε . \end{matrix}$ If $d_{π}$ is the $t^{″}$ -gale defined by $\begin{matrix} d_{π} (w) = 2^{t^{″} | w |} \prod_{i = 1}^{| w |} π (w [0, \dots, i - 1], w [i]) \end{matrix}$ then for any $w \in Σ^{n}$ with $LossRate (π, w) ⩽ t^{'}$ , we have the following, $\begin{array}{l} log d_{π} (w) & = t^{″} n + \sum_{i = 1}^{n} log π (w [1, \dots, i - 1], w [i]) = t^{″} n - {Loss}_{π} (w) ⩾ 1 . \end{array}$ The last inequality holds for all sufficiently large n. Hence, for infinitely many n, $\begin{matrix} D_{n} [d_{π} (w) ⩾ 2] > \frac{1}{2} + ε . \end{matrix}$ Moreover, computation of d involves multiplication of n rational numbers of at most $O (S (n))$ bits each and thus can be implemented by a circuit of size ${(S (n))}^{O (1)}$ [34]. □

Just like dimension, one can also define strong unpredictability in the following way.
Definition 3.5 (Strong unpredictability).

For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , the $(S, ε)$ -strong unpredictability of D is $\begin{array}{l} {sunpred}_{S, ε} (D) = & inf {t \in [0, 1] | for all large enough n, there exists a predictor π of size at most O (S (n)) \\ such that {LossRate}_{ε (n)} (π, D_{n}) ⩽ t} . \end{array}$

Now by following the proof of Theorem 3.4 it is easy to see that a similar relation also holds between strong dimension and strong unpredictability.

Theorem 3.6.
Consider any $s \in [0, 1]$ . For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , if ${sdim}_{S, ε} (D) ⩽ s$ then ${sunpred}_{S^{O (1)}, ε} (D) ⩽ s$ . Conversely, ${sunpred}_{S, ε} (D) ⩽ s$ implies ${sdim}_{S^{O (1)}, ε} (D) ⩽ s$ .

Analogous to pseudorandomness and dimension, for any ensemble of distributions $D = {D_{n}}_{n \in N}$ , one can define weak unpredictability or simply unpredictability (denoted by $unpred (D)$ ) and strong unpredictability (denoted by $sunpred (D)$ ) by allowing $S (n)$ to be $n^{O (1)}$ and $ε (n)$ to be $n^{- O (1)}$ in the Definition 3.3 and 3.5 respectively. Following is a straight forward implication of Theorem 3.4 and Theorem 3.6. Corollary 3.7.
For any ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ , $\begin{matrix} dim (D) = unpred (D) and sdim (D) = sunpred (D) . \end{matrix}$

4. Properties of dimension

We now establish a few basic properties of our notion of dimension. We begin by exhibiting existence of an ensemble of distributions with dimension s, for any $s \in [0, 1]$ .

First, we observe that the dimension of any ensemble of distributions D is the infimum of a non-empty subset of $[0, 1 + ε]$ for any $ε > 0$ and hence the dimension of a distribution is well-defined. The following lemma establishes the above claim.

Lemma 4.1.
For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , ${sdim}_{S, ε} (D) ⩽ 1$ .
Proof.
Let us first take any $s > 1$ such that $2^{s}$ is rational and then consider the following function $d : Σ^{} \to [0, \infty)$ . Let $d (λ) = 1$ and $\forall i \in [n]$ , $d (w [0, \dots, i - 1] 0) = d (w [0, \dots, i - 1] 1) = 2^{s - 1} d (w [0, \dots, i - 1])$ . It is easy to see that d is an s-gale and for any $w \in Σ^{n}$ , $d (w) = 2^{(s - 1) n}$ . Thus for all large enough n, d will $ε (n)$ -succeed over $D_{n}$ . Also note that for all large enough n, this function d can be implemented using a circuit of size $O (n)$ .5
⁵
As for every string w of length n, the value of $d (w)$ will be same, so one can hardcode the value $2^{(s - 1) n}$ inside the non-uniform circuit implementing the function d.

Hence the statement of the lemma follows. □

Above lemma along with Proposition 2.10 implies the following corollary.
Corollary 4.2.
For an ensemble of distributions* $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , ${dim}_{S, ε} (D) ⩽ 1$ .

Since it is clear that any ensemble of distributions has a dimension, the following theorem establishes the fact that our definition yields a nontrivial quantification of the set of ensembles of distributions.
Theorem 4.3.
Let $s \in [0, 1]$ . Then for any $S = S (n) > n$ , $ε = ε (n) > 0$ , there is an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where the distribution $D_{n}$ is on $Σ^{n}$ , such that $(S, ε)$ -dimension (also strong dimension) of D is s.
Proof.
Let us take the ensemble of uniform distributions, i.e., $D : = {U_{n}}_{n \in N}$ , where $U_{n}$ is the uniform distribution on $Σ^{n}$ . Then by Lemma 2.7 together with Lemma 4.1 shows that for any S and ε, ${sdim}_{S, ε} (D) = 1$ . By using Corollary 4.2 instead of Lemma 4.1, one can also show that ${dim}_{S, ε} (D) = 1$ .

On the other hand we consider an ensemble $D = {D_{n}}_{n \in N}$ where support size of each $D_{n}$ is one, or in other words, $D_{n}$ imposes all the probability on a single string, say $0^{n}$ . Now first take any $s > 0$ such that $2^{s}$ is rational and then consider the following function $d : Σ^{} \to [0, \infty)$ . Let $d (λ) = 1$ and $\forall i \in [n]$ , $d (w [0, \dots, i - 1] 0) = 2^{s} d (w [0, \dots, i - 1])$ . It is easy to see that d is an s-gale and $d (0^{n}) = 2^{s n}$ . Thus for all large enough n, d will $ε (n)$ -succeed over $D_{n}$ . Also note that for all large enough n this function d can be implemented using a circuit of size $O (n)$ . Hence for any S and ε, $(S, ε)$ -dimension as well as $(S, ε)$ -strong dimension of D is 0.

Otherwise, assume that $s \in (0, 1)$ . Let us take the ensemble of uniform distributions $D : = {U_{n}}_{n \in N}$ . To each string $x \in Σ^{n}$ , we append $⌊ \frac{n}{s} ⌋ - n$ many zeros, and denote the resulting string as $x^{'}$ . Let $D_{n}^{'} (x^{'}) = U_{n} (x)$ . For strings $y \in Σ^{⌊ \frac{n}{s} ⌋}$ which do not terminate in a sequence of $⌊ \frac{n}{s} ⌋ - n$ many zeros, we set $D_{n}^{'} (y) = 0$ .

For any large enough n, let $π : Σ^{} \times Σ \to [0, 1]$ be the predictor for distribution $U_{n}$ which testifies that the $(S^{O (1)}, ε)$ -strong unpredictability of D is at most 1. Define the new predictor $π^{'} : Σ^{} \times Σ \to [0, 1]$ by $\begin{array}{l} π^{'} (x, b) = \{\begin{matrix} π (x, b) & if | x | < n, b = 0, 1, \\ 1 & if | x | ⩾ n, b = 0, \\ 0 & otherwise . \end{matrix} \end{array}$

For every $w \in Σ^{⌊ \frac{n}{s} ⌋}$ which is in the support of $D_{n}^{'}$ such that $LossRate (π, w [1, \dots, n]) ⩽ (1 + ε_{1})$ , for any $ε_{1} > 0$ , we have that $\begin{matrix} LossRate (π^{'}, w) = \frac{Loss (π, w [1, \dots, n])}{⌊ \frac{n}{s} ⌋} ⩽ \frac{(1 + ε_{1}) n}{⌊ \frac{n}{s} ⌋} ⩽ (s + ε^{'}), for some ε^{'} > 0 . \end{matrix}$ The last inequality holds for all small enough $s / n$ and this testifies that the $(S^{O (1)}, ε)$ -strong unpredictability (hence the $(S^{O (1)}, ε)$ -strong dimension) of the ensemble of distributions $D^{'}$ is at most s. Now by Proposition 2.10, it follows that ${dim}_{S^{O (1)}, ε} (D^{'})$ is also at most s.

Now, assume that $(S, ε)$ -dimension of $D^{'}$ is less than s. For any $s^{'}$ such that $0 < s^{'} < s$ , for infinitely many n, there exists an $s^{'}$ -gale d of size at most $O (S (n))$ which $ε (n)$ -succeeds on $D_{n}^{'}$ . We show that this would imply that $U_{n}$ is not uniform. Now consider a string $w \in Σ^{⌊ \frac{n}{s} ⌋}$ , which is in the support of $D_{n}^{'}$ . For any $k \in {n + 1, \dots, ⌊ \frac{n}{s} ⌋}$ , $d (w [1, \dots, k]) ⩽ 2^{s^{'}} d (w [1, \dots, k - 1])$ and thus $d (w) ⩾ 2$ will imply that $d (w [1, \dots, n]) ⩾ 2^{- s^{'} (⌊ \frac{n}{s} ⌋ - n) + 1}$ . Now consider the martingale $d^{'}$ (needs not be computed by any circuit) corresponding to the $s^{'}$ -gale d. According to [22], we have $d^{'} (w^{'}) = 2^{(1 - s^{'}) ∣ w^{'} ∣} d (w^{'})$ , for any string $w^{'} \in Σ^{}$ . Thus, $\begin{array}{l} D_{n}^{'} [d^{'} (w [1, \dots, n]) ⩾ 2] & ⩾ D_{n}^{'} [d (w [1, \dots, n]) ⩾ 2^{- s^{'} (⌊ \frac{n}{s} ⌋ - n) + 1}] \\ ⩾ D_{n}^{'} [d (w) ⩾ 2] \\ > \frac{1}{2} + ε (n) . \end{array}$ Note that $D_{n}^{'} [d^{'} (w [1, \dots, n]) ⩾ 2]$ is same as $U_{n} [d^{'} (x) ⩾ 2]$ , which contradicts the fact that by Markov inequality, $U_{n} [d^{'} (x) ⩾ 2] ⩽ \frac{1}{2}$ . This shows that ${dim}_{S, ε} (D^{'}) ⩾ s$ and hence by Proposition 2.10, ${sdim}_{S, ε} (D^{'})$ is also greater than or equal to s. □

Informally the following theorem shows that our notion of dimension is able to capture the fact that if we mix a “good” distribution with a small amount of an extremely “bad” distribution, then also “quality” of the first distribution would not change much.
Theorem 4.4.
Let $D = {D_{n}}_{n \in N}$ , $D^{1} = {D_{n}^{1}}_{n \in N}$ and $D^{2} = {D_{n}^{2}}_{n \in N}$ be three ensembles of distributions such that for some $δ = δ (n) \in [0, 1]$ , for every $n \in N$ , $D_{n} = (1 - δ (n)) D_{n}^{1} + δ (n) D_{n}^{2}$ . If for any $S = S (n) > n$ and $ε = ε (n) > 0$ , ${dim}_{S, ε} (D^{1}) = s_{1}$ $({sdim}_{S, ε} (D^{1}) = s_{1})$ , then ${dim}_{S, (ε + δ)} (D) ⩾ s_{1}$ $({sdim}_{S, (ε + δ)} (D) ⩾ s_{1})$ . 6
⁶
Note that bias term in the dimension of $D^{1}$ depends on δ.

Proof.
For the contrary, let us assume that, ${dim}_{S, (ε + δ)} (D) < s_{1}$ and assume $s = s_{1} - ε_{1}$ , for some $ε_{1}$ , $0 < ε_{1} < s_{1}$ . So for infinitely many n, there exists an s-gale of size at most $O (S (n))$ that $(ε (n) + δ (n))$ -succeeds over $D_{n}$ . Thus, $\begin{matrix} D_{n} [d (w) ⩾ 2] > \frac{1}{2} + (ε (n) + δ (n)) . \end{matrix}$

Let the strings w for which $d (w) ⩾ 2$ holds be $w_{i}$ , $1 ⩽ i ⩽ k$ . So, $\begin{matrix} D_{n} (w_{1}) + \dots + D_{n} (w_{k}) > \frac{1}{2} + (ε (n) + δ (n)), \end{matrix}$ where $D_{n} (w_{i}) = (1 - δ (n)) D_{n}^{1} (w_{i}) + δ (n) D_{n}^{2} (w_{i})$ , for all $1 ⩽ i ⩽ k$ .

Now, as $D_{n}^{2} (w_{1}) + \dots + D_{n}^{2} (w_{k}) ⩽ 1$ , $\begin{matrix} D_{n}^{1} (w_{1}) + \dots + D_{n}^{1} (w_{k}) > \frac{1}{2} + ε (n) \end{matrix}$ and thus ${dim}_{S, ε} (D^{1}) < s_{1}$ which is a contradiction.

The above argument is valid for all n for which there exists an s-gale of size at most $O (S (n))$ that $(ε (n) + δ (n))$ -succeeds over $D_{n}$ and hence the same claim holds even if we consider strong dimension instead of dimension. □

If we follow the proof of Theorem 4.4 with martingale instead of s-gale, we get the following weaker version of the above theorem, which we will require in the construction of deterministic extractor for a special kind of sources in Section 6.1.
Lemma 4.5.
Let $D = {D_{n}}_{n \in N}$ , $D^{1} = {D_{n}^{1}}_{n \in N}$ and $D^{2} = {D_{n}^{2}}_{n \in N}$ be three ensembles of distributions such that for some $δ = δ (n) \in [0, 1]$ , for every $n \in N$ , $D_{n} = (1 - δ (n)) D_{n}^{1} + δ (n) D_{n}^{2}$ . If for any $S = S (n) > n$ and $ε = ε (n) > 0$ , $D^{1}$ is $(S, ε)$ -pseudorandom, then D is $(S, ε + δ)$ -pseudorandom.

In subsequent sections, we will see how to extract pseudorandom parts from a convex combination of distributions. For that purpose we need the following lemma which establishes the fact that convex combination of two pseudorandom distributions will be pseudorandom as well.
Lemma 4.6.
Consider two ensembles of distributions $D^{1} = {D_{n}^{1}}_{n \in N}$ and $D^{2} = {D_{n}^{2}}_{n \in N}$ . Suppose for any $S = S (n) > n$ and $ε = ε (n) > 0$ , both $D^{1}$ and $D^{2}$ are $(S, ε)$ -pseudorandom. If for $δ = δ (n) \in [0, 1]$ there exists an ensemble of distributions $D = {D_{n}}_{n \in N}$ which can be expressed as for all $n \in N$ , $D_{n} = δ (n) D_{n}^{1} + (1 - δ (n)) D_{n}^{2}$ , then D is also $(S, ε^{'})$ -pseudorandom, where $ε^{'} (n) = n \cdot ε (n)$ . 7
⁷
Note that this lemma will be useful only when we consider $ε (n) < \frac{1}{2 n}$ .

Proof.
The claim clearly holds when $δ (n)$ is either 0 or 1, so assume that $0 < δ (n) < 1$ . For the contrary, let us assume that D is not $(S, ε^{'})$ -pseudorandom where $ε^{'} (n) = n \cdot ε (n)$ , i.e., by Lemma 2.7, for infinitely many $n \in N$ there exists an martingale d of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}$ , i.e., $\begin{matrix} D_{n} [d (w) ⩾ 2] > \frac{1}{2} + ε (n) . \end{matrix}$ As $D^{2}$ is $(S, ε)$ -pseudorandom, by Lemma 2.7, for all large enough n there exists no martingale of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}^{2}$ . Thus it is possible to consider an $n \in N$ such that there exists a martingale d of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}$ , but does not $ε (n)$ -succeed on $D_{n}^{2}$ . Let the strings $w \in Σ^{n}$ for which $d (w) ⩾ 2$ holds be $w_{i}$ , $1 ⩽ i ⩽ k$ . So, $\begin{matrix} D_{n} (w_{1}) + \dots + D_{n} (w_{k}) > \frac{1}{2} + ε (n), \end{matrix}$ where $D_{n} (w_{i}) = δ (n) D_{n}^{1} (w_{i}) + (1 - δ (n)) D_{n}^{2} (w_{i})$ , $1 ⩽ i ⩽ k$ . Now, since we have that $\begin{matrix} D_{n}^{2} (w_{1}) + \dots + D_{n}^{2} (w_{k}) ⩽ \frac{1}{2} + ε (n) . \end{matrix}$ Thus the following holds $\begin{matrix} D_{n}^{1} (w_{1}) + \dots + D_{n}^{1} (w_{k}) > \frac{1}{2} + ε (n) . \end{matrix}$ As for infinitely many $n \in N$ the above happens, so $D^{1}$ is not $(S, ε)$ -pseudorandom, which is a contradiction. □

We can also slightly generalize the above lemma and get the following theorem.
Theorem 4.7.
Let $D = {D_{n}}_{n \in N}$ , $D^{1} = {D_{n}^{1}}_{n \in N}$ and $D^{2} = {D_{n}^{2}}_{n \in N}$ be three ensembles of distributions such that for some $δ = δ (n) \in [0, 1]$ , for every $n \in N$ , $D_{n} = δ (n) D_{n}^{1} + (1 - δ (n)) D_{n}^{2}$ . Then for any $S = S (n) > n$ and $ε = ε (n) > 0$ , $\begin{matrix} {dim}_{S, ε} (D) ⩾ min {{dim}_{S, ε} (D^{1}), {dim}_{S, ε} (D^{2})} . \end{matrix}$
Proof.
The claim clearly holds when $δ (n)$ is either 0 or 1, so assume that $0 < δ (n) < 1$ . Let ${dim}_{S, ε} (D_{1}) = s_{1}$ , and ${dim}_{S, ε} (D_{2}) = s_{2}$ .

For the contrary, let us assume that, ${dim}_{S, ε} (D) < min {s_{1}, s_{2}}$ . Now consider $s = min {s_{1}, s_{2}} - ε_{1}$ , for some $ε_{1}$ , $0 < ε_{1} < min {s_{1}, s_{2}}$ . Then for infinitely many n, there exists an s-gale d of size at most $O (S (n))$ such that $\begin{matrix} D_{n} [d (w) ⩾ 2] > \frac{1}{2} + ε (n) . \end{matrix}$ As ${dim}_{S, ε} (D^{2}) = s_{2}$ , so for all large enough n, there exists no s-gale of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}^{2}$ . Thus we can consider an n such that there exists an s-gale d of size at most $O (S (n))$ that $ε (n)$ -succeeds on $D_{n}$ , but does not $ε (n)$ -succeed on $D_{n}^{2}$ . Let the strings w for which $d (w) ⩾ 2$ holds be $w_{i}$ , $1 ⩽ i ⩽ k$ . So, $\begin{matrix} D_{n} (w_{1}) + \dots + D_{n} (w_{k}) > \frac{1}{2} + ε (n), \end{matrix}$ where $D_{n} (w_{i}) = δ (n) D_{n}^{1} (w_{i}) + (1 - δ (n)) D_{n}^{2} (w_{i})$ , for $1 ⩽ i ⩽ k$ . Also, we have that $\begin{matrix} D_{n}^{2} (w_{1}) + \dots + D_{n}^{2} (w_{k}) ⩽ \frac{1}{2} + ε (n) . \end{matrix}$ Thus $\begin{matrix} D_{n}^{1} (w_{1}) + \dots + D_{n}^{1} (w_{k}) > \frac{1}{2} + ε (n) \end{matrix}$ and this happens for infinitely many $n \in N$ implying ${dim}_{S, ε} (D^{1}) < s_{1}$ , which is a contradiction. □

The following theorem shows that in order for a distribution to have dimension less than 1, it is not sufficient to have a few positions where we can successfully predict – it is necessary that these positions occur often.
Theorem 4.8.
For any $S = S (n) > n$ and $ε = ε (n) > 0$ , there is an ensemble of distributions $D = {D_{n}}_{n \in N}$ such that ${dim}_{S, ε} (D) = 1$ , but D is not $(S, ε)$ -pseudorandom.
Proof.
Let $D_{n}$ on $Σ^{n}$ be defined as follows. $\begin{array}{l} D_{n} (x) & = \{\begin{matrix} \frac{1}{2^{n - 1}} & if x [n] = 0 \\ 0 & otherwise. \end{matrix} \end{array}$ Then D is clearly not $(S, ε)$ -pseudorandom, for any value of $S = S (n) > n$ and $ε = ε (n) > 0$ . Consider a predictor $π : Σ^{} \times Σ \to [0, 1]$ defined as follows. For strings w of length i, $i \in [1, n - 2]$ , set $π (w, b) = 0.5$ , $b = 0, 1$ and $π (w, 0) = 1$ , $π (w, 1) = 0$ otherwise. Then $\begin{matrix} D_{n} [π (x [1, \dots, n - 1], x [n]) = 1] = 1 . \end{matrix}$

However, we will show that ${dim}_{S, ε} (D) = 1$ . Assume that ${dim}_{S, ε} (D) < 1$ and thus for some $ε_{1}$ , $0 < ε_{1} < 1$ , for infinitely many $n \in N$ , there exists an s-gale d, where $s = 1 - ε_{1}$ , of size at most $O (S (n))$ which $ε (n)$ -succeeds on $D_{n}$ . Now consider a string $w \in Σ^{n}$ , which is in the support of $D_{n}$ . Now, $d (w) ⩽ 2^{s} d (w [1, \dots, n - 1])$ and thus $d (w) ⩾ 2$ will imply that $d (w [1, \dots, n - 1]) ⩾ 2^{1 - s}$ . Next consider the martingale $d^{'}$ (needs not be computed by any circuit) corresponding to the s-gale d. According to [22], we have $d^{'} (w^{'}) = 2^{(1 - s) ∣ w^{'} ∣} d (w^{'})$ , for any string $w^{'} \in Σ^{}$ . Thus, $\begin{array}{l} D_{n} [d^{'} (w [1, \dots, n - 1]) ⩾ 2] & ⩾ D_{n} [d (w [1, \dots, n - 1]) ⩾ 2^{1 - s}] \\ ⩾ D_{n} [d (w) ⩾ 2] \\ > \frac{1}{2} + ε (n) . \end{array}$ The first inequality holds for all large enough n. Note that $D_{n} [d^{'} (w [1, \dots, n - 1]) ⩾ 2]$ is same as $U_{n - 1} [d^{'} (x) ⩾ 2]$ , where $x \in Σ^{n - 1}$ is drawn according to the distribution $U_{n - 1}$ . However by Markov inequality, $U_{n - 1} [d^{'} (x) ⩾ 2] ⩽ \frac{1}{2}$ , which is a contradiction and this completes the proof. □

We now give separation between two notions of dimension by providing an example of ensemble which has a very high strong dimension, but very low weak dimension. Theorem 4.9.
There exists an ensemble of distributions $D = {D_{n}}_{n \in N}$ such that for any $S = S (n) > n$ and $ε = ε (n) > 0$ , ${dim}_{S, ε} (D) < {sdim}_{S, ε} (D)$ .
Proof.
Here we actually show a much stronger claim by giving an example of an ensemble of distributions $D = {D_{n}}_{n \in N}$ such that ${sdim}_{S, ε} (D) = 1$ whereas ${dim}_{S, ε} (D) = 0$ . This is the largest possible gap between weak and strong dimension of any ensemble of distributions.

Construct an ensemble of distributions $D = {D_{n}}_{n \in N}$ as follows: for all the odd value of n, set $D_{n} = U_{n}$ where $U_{n}$ is the uniform distribution over $Σ^{n}$ and for all even value of n, set $D_{n}$ to be such that it imposes all the probability on a single string $0^{n}$ .

Due to Markov inequality, there exists no martingale that $ε (n)$ -succeeds over distribution $D_{n}$ for any odd value of n and by Lemma 4.1, strong dimension can be at most 1. Hence, ${sdim}_{S, ε} (D) = 1$ . By the argument used in the proof of Theorem 4.3, we can say that for any $s > 0$ such that $2^{s}$ is rational, for all large enough even value of n, there exists an s-gale of size at most $O (S (n))$ that $ε (n)$ -succeeds over $D_{n}$ and hence ${dim}_{S, ε} (D) = 0$ . □

5. Pseudoentropy and dimension

In this section we study the relation between our notion of dimension and different variants of computational or pseudo (min/Shannon) entropy. We will use standard notions and notations of information theory (e.g., Shannon entropy, KL divergence) without defining them. Readers can find a few basic notations and propositions of information theory in the following subsection and for more details, we refer the reader to the book by Cover and Thomas [8].

5.1. Basics of information theory

Definition 5.1 (Shannon entropy).

The Shannon entropy of a discrete random variable X is defined as $\begin{matrix} H (X) : = - \sum_{x} \Pr [X = x] log \Pr [X = x] = - E_{x \sim X} [log \Pr [X = x]] . \end{matrix}$ The joint entropy $H (X, Y)$ is defined to be $- E_{x \sim X, y \sim Y} [log \Pr [X = x, Y = y]]$ and the conditional entropy $H (Y ∣ X)$ is defined to be $E_{x \sim X} [H (Y ∣ X = x)]$ .

Proposition 5.2 (Chain rule for Shannon entropy).

$\begin{matrix} H (X, Y) = H (X) + H (Y ∣ X) . \end{matrix}$

Definition 5.3 (KL divergence).

The Kullback–Leibler distance or KL divergence between two distributions P and Q is defined as $\begin{matrix} KL (P ‖ Q) : = E_{p \sim P} log \frac{\Pr [P = p]}{\Pr [Q = p]} . \end{matrix}$

Definition 5.4 (Conditional KL divergence).

For random variables $(P_{1}, P_{2})$ and $(Q_{1}, Q_{2})$ , the conditional KL divergence from $(P_{2} | P_{1})$ to $(Q_{2} | Q_{1})$ is defined as $\begin{matrix} KL ((P_{2} | P_{1}) ‖ (Q_{2} | Q_{1})) = E_{p_{1} \sim P_{1}, p_{2} \sim P_{2}} [log \frac{\Pr [P_{2} = p_{2} | P_{1} = p_{1}]}{\Pr [Q_{2} = p_{2} | Q_{1} = p_{1}]}] . \end{matrix}$

Just like Shannon entropy, in this case also, we have chain rule stated below.

Proposition 5.5 (Chain rule for KL divergence).

$\begin{matrix} KL (P_{1}, P_{2} ‖ Q_{1}, Q_{2}) = KL (P_{1} ‖ Q_{1}) + KL ((P_{2} | P_{1}) ‖ (Q_{2} | Q_{1})) . \end{matrix}$

5.2. High HILL-type pseudo min-entropy implies high dimension

For a distribution D, the min-entropy of D is defined as $H_{\infty} (D) = {min}_{w} {log (1 / D [w])}$ . We start with the standard definition of computational min-entropy, as given by [13].

Definition 5.6 (HILL-type pseudo min-entropy).

For any $S = S (n) > n$ and $ε = ε (n) > 0$ , an ensemble of distributions $D = {D_{n}}_{n \in N}$ has $(S, ε)$ -HILL-type pseudo min-entropy (or simply $(S, ε)$ -pseudo min-entropy) at least $k = k (n)$ , denoted as $H_{\infty}^{HILL, S, ε} (D) ⩾ k$ if there exists an ensemble of distributions $D^{'} = {D_{n}^{'}}_{n \in N}$ such that for all large enough n,

$H_{\infty} (D_{n}^{'}) ⩾ k (n)$ , and

$D_{n}^{'}$ is $(O (S (n)), ε (n))$ -indistinguishable from the distribution $D_{n}$ .

Several other definitions of pseudo min-entropy (metric-type, Yao-type or compression type) are present in the literature. We refer the reader to [4] for a comprehensive treatment on different definitions and the connections between them. In the remaining portion of this subsection, we focus only on HILL-type pseudo min-entropy. Now we state the main result of this subsection.

Theorem 5.7.
For every ensemble of distributions $D = {D_{n}}_{n \in N}$ and for any $S = S (n) > n$ , $ε = ε (n) > 0$ , if $H_{\infty}^{HILL, S, ε} (D) ⩾ k$ , where $k = k (n) = s n$ for some $s \in [0, 1]$ , then ${dim}_{S, ε} (D) ⩾ s$ .
Proof.
The theorem is a consequence of the following lemma. Lemma 5.8.
For every ensemble of distributions $X = {X_{n}}_{n \in N}$ , if for all large enough n, $H_{\infty} (X_{n}) ⩾ k (n)$ , where $k (n) = s n$ for some $s \in [0, 1]$ , then ${dim}_{S, ε} (X) ⩾ s$ for any $S = S (n) > n$ and $ε = ε (n) > 0$ .

Now observe that if for all large enough n, distribution $D_{n}$ is $(O (S (n)), ε (n))$ -indistinguishable from another distribution $D_{n}^{'}$ , then ${dim}_{S, ε} (D) = {dim}_{S, ε} (D^{'})$ as otherwise the s-gale of size at most $O (S (n))$ which $ε (n)$ -succeeds over exactly one of them, acts as a distinguishing circuit. This fact along with Lemma 5.8 completes the proof. □

It only remains to establish Lemma 5.8.
Proof of Lemma 5.8.
For the sake of contradiction, let us assume that for infinitely many $n \in N$ , there exists an s-gale d of size at most $O (S (n))$ that $ε (n)$ -succeeds over $X_{n}$ , i.e., $\begin{matrix} X_{n} [d (w) ⩾ 2] > \frac{1}{2} + ε (n) . \end{matrix}$ Now consider the following set $\begin{matrix} S : = {w \in Σ^{n} ∣ d (w) ⩾ 2} . \end{matrix}$ As $H_{\infty} (X_{n}) ⩾ k (n)$ , $\begin{matrix} | S | > 2^{s n - 1} + 2^{s n} \cdot ε (n) . \end{matrix}$ By taking the corresponding martingale $d^{'}$ (needs not be computed by any circuit) according to the Proposition 2.4, we have that for any $w \in S$ , $d^{'} (w) ⩾ 2^{(1 - s) n + 1}$ and as a consequence, $\begin{matrix} U_{n} [d^{'} (w) ⩾ 2^{(1 - s) n + 1}] > 2^{s n - n - 1} + 2^{s n - n} \cdot ε (n) \end{matrix}$ which contradicts the fact that by Markov inequality, $U_{n} [d^{'} (w) ⩾ 2^{(1 - s) n + 1}] ⩽ 2^{s n - n - 1}$ . □

One can extend the definition of HILL-type pseudo min-entropy by allowing $S (n)$ to be $n^{O (1)}$ and $ε (n)$ to be $n^{- O (1)}$ and let us denote this by $H_{\infty}^{HILL} (D)$ . We can extend the result stated in Theorem 5.7 as follows.
Corollary 5.9.
For any ensemble of distributions $D = {D_{n}}_{n \in N}$ , where $D_{n}$ is a distribution over $Σ^{n}$ , and $s \in [0, 1]$ , if $H_{\infty}^{HILL} (D_{n}) ⩾ k$ , where $k = k (n) = s n$ , then $dim (D) ⩾ s$ .

The converse direction of the statement of Theorem 5.7 is also true if the distribution under consideration is pseudorandom. If the converse is true then we can apply any randomness extractor to get pseudorandom distribution from any distribution having high dimension [4]. However, we should always be careful about the circuit size with respect to which we call the output distribution pseudorandom. Unfortunately, in general the converse is not true. Counterexample for the converse.
Suppose one-way functions (see Definition 2.2.1 of [10]) exist, then it is well-known that we can construct a pseudorandom generator (see Definition 3.3.1 of [10]) $G = {G_{l}}_{l \in N}$ where $G_{l} : Σ^{l} \to Σ^{m}$ such that m is any polynomial in l, say $m = l^{3}$ . For the construction of pseudorandom generator with polynomial stretch from any one-way function, interested reader may refer to [13,33]. Now consider the ensemble of distributions $D : = {(G (U_{l}), U_{l})}_{l \in N}$ . For large enough l, using the argument similar to the proof of Theorem 4.3, it can easily be shown that the distribution D has dimension (as well as weak dimension) almost 1 as the distribution on the first m bits are pseudorandom, but pseudo min-entropy is not larger than l.

5.3. Equivalence between dimension and next-bit pseudo Shannon entropy

In the last subsection, we have talked about pseudo min-entropy. In similar fashion, one can also define pseudo Shannon entropy and a natural generalization of it is conditional pseudo Shannon entropy [12,17,33].

Definition 5.10 (Conditional pseudo Shannon entropy).

A random variable $Y_{n}$ jointly distributed with $X_{n}$ is said to have $(S, ε)$ -conditional pseudo Shannon entropy at least k, for any $S \in N$ and $ε > 0$ if there exists a random variable $Z_{n}$ jointly distributed with $X_{n}$ such that

$H (Z_{n} | X_{n}) ⩾ k$ , and

$(X_{n}, Y_{n})$ and $(X_{n}, Z_{n})$ are $(S, ε)$ -indistinguishable.

Now suppose

Y = {Y_{n}}_{n \in N}

is an ensemble of random variables jointly distributed with another ensemble of distributions

X = {X_{n}}_{n \in N}

. For any

S = S (n) > n

and

ε = ε (n) > 0

, Y is said to have

(S, ε)

-conditional pseudo Shannon entropy at least

k = k (n)

given X if there exists another ensemble of distributions Z jointly distributed with X such that for all sufficiently large n,

Y_{n}

has

(O (S (n)), ε (n))

-conditional pseudo Shannon entropy at least

k (n)

The following is the variant of pseudoentropy that we are looking for in this subsection and was introduced by Haitner et al. [12].

Definition 5.11 (Next-bit pseudo Shannon entropy).

An ensemble of random variables $X = {X_{n}}_{n \in N}$ , where $X_{n} = (X_{n}^{1}, X_{n}^{2}, \dots, X_{n}^{n})$ takes values in $Σ^{n}$ , has $(S, ε)$ -next-bit pseudo Shannon entropy for any $S = S (n) > n$ and $ε = ε (n) > 0$ at least $k = k (n)$ , denoted as $H^{next, S, ε} (X) ⩾ k$ if there exists an ensemble of random variables $Y = {Y_{n}}_{n \in N}$ where $Y_{n} = (Y_{n}^{1}, Y_{n}^{2}, \dots, Y_{n}^{n})$ takes values in $Σ^{n}$ and for all sufficiently large n,

$\sum_{i} H (Y_{n}^{i} | X_{n}^{1}, \dots, X_{n}^{i - 1}) ⩾ k (n)$ , and

for all $1 ⩽ i ⩽ n$ , $(X_{n}^{1}, \dots, X_{n}^{i - 1}, X_{n}^{i})$ and $(X_{n}^{1}, \dots, X_{n}^{i - 1}, Y_{n}^{i})$ are $(O (S (n)), ε (n))$ -indistinguishable.

Later, Vadhan and Zheng [33] provided an alternative characterization of conditional pseudo Shannon entropy by showing an equivalence between it and KL-hardness (defined below). We use this alternative characterization extensively for our purpose.

Definition 5.12 (KL-hardness).

Suppose $(X_{n}, Y_{n})$ is a $Σ^{n} \times Σ$ -valued random variable and π be any predictor. Then π is said to be a δ-KL-predictor of $Y_{n}$ given $X_{n}$ if $KL (X_{n}, Y_{n} ‖ X_{n}, C_{π}) ⩽ δ$ where $C_{π} (y | x) = π (x, y)$ for all $x \in Σ^{n}$ and $y \in Σ$ .

Moreover, for any $S = S (n) > n$ and $δ = δ (n) > 0$ , an ensemble $Y = {Y_{n}}_{n \in N}$ , where each $Y_{n}$ is a random variable taking value in Σ, is said to be $(S, δ)$ -KL-hard given another ensemble of random variables $X = {X_{n}}_{n \in N}$ , where each $X_{n}$ takes value in $Σ^{n}$ , if for all large enough n there is no predictor π of size at most $O (S (n))$ that is a $δ (n)$ -KL-predictor of $Y_{n}$ given $X_{n}$ .

The following theorem provides the equivalence among KL-hardness and conditional pseudo Shannon entropy of a distribution.

Theorem 5.13 ([33]).

For an ensemble $(X, Y) = {(X_{n}, Y_{n})}_{n \in N}$ where each $(X_{n}, Y_{n})$ is a $Σ^{n} \times Σ$ -valued random variable and for any $δ = δ (n) > 0$ , $ε = ε (n) > 0$ ,

If Y is $(S, δ)$ -KL-hard given X, then for all large enough n, $Y_{n}$ has $(S^{'} (n), ε (n))$ -conditional pseudo Shannon entropy at least $H (Y_{n} | X_{n}) + δ (n) - ε (n)$ , where $S^{'} (n) = S {(n)}^{Ω (1)} / poly (n, 1 / ε (n))$ .

Conversely, if for all large enough n, $Y_{n}$ has $(S (n), ε (n))$ -conditional pseudo Shannon entropy at least $H (Y_{n} | X_{n}) + δ (n)$ , then for every $σ = σ (n) > 0$ , Y is $(S^{'}, δ^{'})$ -KL-hard given X, where $S^{'} (n) = min {S {(n)}^{Ω (1)} / poly (n, log (1 / σ (n))), Ω (σ (n) / ε (n))}$ and $δ^{'} (n) = δ (n) - σ (n)$ .

Now we are ready to state the main theorem of this subsection which conveys the fact that the distributions with high dimensions also have high next-bit pseudo Shannon entropy.

Theorem 5.14.
For an ensemble of distributions $D = {D_{n}}_{n \in N}$ , where $D_{n}$ is a distribution over $Σ^{n}$ , for any $S = S (n) > n$ and $ε = ε (n) > 0$ such that $ε (n) \to 0$ as $n \to \infty$ , if ${dim}_{S, ε} (D) > 2 s$ , then $H^{next, S^{'}, ε} (D) > k$ , where $k = k (n) = s n$ and $S^{'} (n) = S {(n)}^{Ω (1)} / poly (n, 1 / ε (n))$ . 8
⁸
Note that $Ω (1)$ constant in the expression of $S^{'} (n)$ here is related to that appeared in Item 1 of Theorem 5.13, but not exactly the same.

Proof.
For the sake of contradiction, let us assume that $H^{next, S^{'}, ε} (D) ⩽ k$ . Thus there exists a subset $S \subseteq N$ of cardinality equals to the cardinality of $N$ such that for all $n \in S$ , Item 1 and Item 2 of Definition 5.11 do not hold simultaneously. On the other hand ${dim}_{S, ε} (D) > 2 s$ and thus by following the proof of Theorem 3.4, we can say that there exists a $c \in (0, 1)$ such that ${unpred}_{S^{c}, ε} (D) = t > 2 s$ . Now consider some large enough n belongs to S and break $D_{n}$ into 1-bit blocks, i.e., $D_{n} = (D_{n}^{1}, D_{n}^{2}, \dots, D_{n}^{n})$ .

For any predictor $π : Σ^{} \times Σ \to [0, 1]$ , let us define $π_{i} : Σ^{i - 1} \times Σ \to [0, 1]$ such that $π (x, a) = π_{i} (x, a), \forall_{x \in Σ^{i - 1}, a \in Σ}$ for $1 ⩽ i ⩽ n$ . Then, $\begin{array}{l} \sum_{i = 1}^{n} KL ((D_{n}^{1}, \dots, D_{n}^{i - 1}), D_{n}^{i} ‖ (D_{n}^{1}, \dots, D_{n}^{i - 1}), π_{i}) \\ = \sum_{i = 1}^{n} [\sum_{w_{i} \in Σ^{i}} - log (π_{i} (w_{i} [1 \dots i - 1], w_{i} [i])) \Pr [w_{i}] - H (D_{n}^{i} | D_{n}^{1} \dots D_{n}^{i - 1})] \\ = \sum_{i = 1}^{n} [\sum_{w_{i} \in Σ^{i}} loss (π (w_{i} [1 \dots i - 1], w_{i} [i])) \Pr [w_{i}] - H (D_{n}^{i} | D_{n}^{1} \dots D_{n}^{i - 1})] \\ = \sum_{w \in Σ^{n}} Loss (π, w) D_{n} (w) - H (D_{n}), \end{array}$ where the last equality follows from the chain rule of Shannon entropy (Proposition 5.2).

Now the definitions of next-bit pseudo Shannon entropy, conditional pseudo Shannon entropy and KL-predictor along with Item 1 of Theorem 5.13 imply that for any $n \in S$ , there exists a predictor π of size at most $O ({(S (n))}^{c})$ such that $\begin{matrix} \sum_{w \in Σ^{n}} Loss (π, w) D_{n} (w) ⩽ (s + ε (n)) n . \end{matrix}$

Hence for any $ε_{1} > 0$ , $\begin{array}{l} D_{n} [LossRate (π, w) ⩾ (t - ε_{1})] & = D_{n} [Loss (π, w) ⩾ (t - ε_{1}) n] \\ ⩽ \frac{\sum_{w \in Σ^{n}} Loss (π, w) D_{n} (w)}{(t - ε_{1}) n} by Markov inequality \\ ⩽ \frac{s + ε (n)}{t - ε_{1}} . \end{array}$ Thus, $\begin{matrix} D_{n} [LossRate (π, w) ⩽ (t - ε_{1})] ⩾ 1 - \frac{s + ε (n)}{t - ε_{1}} . \end{matrix}$ As ${unpred}_{S^{c}, ε} (D) = t$ , by the definition, it implies that for all but finitely many n belong to the set S, $\begin{matrix} 1 - \frac{s + ε (n)}{t - ε_{1}} ⩽ \frac{1}{2} + ε (n) . \end{matrix}$ For all large enough n, the above inequality gives us $t ⩽ 2 s + ε_{2}$ , for any $ε_{2} > ε_{1}$ because $ε (n) \to 0$ as $n \to \infty$ . Hence ${unpred}_{S^{c}, ε} (D) ⩽ 2 s$ which is a contradiction and this completes the proof. □

The following weak converse can easily be proven.
Theorem 5.15.
For an ensemble of distributions* $D = {D_{n}}_{n \in N}$ , where $D_{n}$ is a distribution over $Σ^{n}$ , for any $S = S (n) > n$ and $ε = ε (n) > 0$ , if $H^{next, S, ε} (D) > s n$ , then for any $ε^{'} > 0$ ${dim}_{S^{'}, ε} (D) > s - \frac{1}{2} - ε^{'}$ , where $S^{'} (n) = min {{(S (n))}^{Ω (1)} / poly (n), 1 / ε {(n)}^{Ω (1)}}$ . 9
⁹
Note that $Ω (1)$ constant of the term $S {(n)}^{Ω (1)}$ here is related to that appeared in Item 2 of Theorem 5.13, but not exactly the same.

Proof.
Suppose an ensemble of distributions D is given such that $H^{next, S, ε} (D) > s n$ . Now take any large enough n and break $D_{n}$ into 1-bit blocks, i.e., $D_{n} = (D_{n}^{1}, D_{n}^{2}, \dots, D_{n}^{n})$ . Let us denote ${dim}_{S^{'}, ε} (D) = t$ and thus by Theorem 3.4, there exists a constant $c > 1$ such that ${unpred}_{{S^{'}}^{c}, ε} (D) ⩽ t$ . This implies that for infinitely many n, there exists a predictor π of size at most $O ({S^{'}}^{c} (n))$ such that for any $ε_{1} > 0$ , $\begin{matrix} D_{n} [LossRate (π, w) ⩽ (t + ε_{1})] > \frac{1}{2} + ε (n) . \end{matrix}$ Thus we can write the following, $\begin{matrix} \sum_{w \in Σ^{n}} Loss (π, w) D_{n} (w) ⩽ (t + ε_{1}) n + (\frac{1}{2} - ε (n)) n . \end{matrix}$

We have already seen that for any predictor $π : Σ^{} \times Σ \to [0, 1]$ , $\begin{matrix} \sum_{i = 1}^{n} KL ((D_{n}^{1}, \dots, D_{n}^{i - 1}), D_{n}^{i} ‖ (D_{n}^{1}, \dots, D_{n}^{i - 1}), π_{i}) = \sum_{w \in Σ^{n}} Loss (π, w) D_{n} (w) - H (D_{n}) . \end{matrix}$

Now the definitions of next-bit pseudo Shannon entropy, conditional pseudo Shannon entropy and KL-predictor along with Item 2 of Theorem 5.13 imply that for all large enough n, for every $σ (n) > 0$ , $\begin{matrix} \sum_{w \in Σ^{n}} Loss (π, w) D_{n} (w) > (s - σ (n)) n . \end{matrix}$

Hence, $\begin{array}{l} (s - σ (n)) n < (t + ε_{1}) n + (\frac{1}{2} - ε (n)) n \\ \Rightarrow s < t + \frac{1}{2} + ε_{2} \end{array}$ for any $ε_{2} > ε_{1}$ , for infinitely many large enough n and now setting $S^{'} (n)$ to be such that $S^{'} {(n)}^{c}$ equals to the value of $S^{'} (n)$ mentioned in Item 2 of Theorem 5.13 concludes the proof. □

It is natural to allow $S (n)$ to be $n^{O (1)}$ and $ε (n)$ to be $n^{- O (1)}$ and then consider the definitions of conditional pseudo Shannon entropy, next-bit pseudo Shannon entropy (denoted as $H^{next} (D)$ ) and KL-hardness. For details we refer the reader to [33]. Now we use the equivalence between conditional pseudo Shannon entropy and KL-hardness from [33] to derive the following corollary of Theorem 5.14.
Corollary 5.16.
For any ensemble of distributions* $D = {D_{n}}_{n \in N}$ , where $D_{n}$ is a distribution over $Σ^{n}$ , and for any $s \in [0, 1]$ , if $dim (D_{n}) > 2 s$ , then $H^{next} (D) > k$ for $k = k (n) = s n$ .

In a similar fashion, we get the following as a corollary of Theorem 5.15. Corollary 5.17.
For any $ε > 0$ , $s \in [0, 1]$ and $k = k (n) = s n$ , for any ensemble of distributions $D = {D_{n}}_{n \in N}$ , where $D_{n}$ is a distribution over $Σ^{n}$ , if $H^{next} (D) > k$ , then $dim (D) > s - \frac{1}{2} - ε$ .

6. Pseudorandom extractors and lower bound

We now introduce the notion of pseudorandom extractor similar to the notion of randomness extractor. Intuitively, a randomness extractor is a function that outputs almost random (statistically close to uniform) bits from weakly random sources, which need not be close to the uniformly random source. Two distributions X and Y on a set Λ are said to be ε-close (statistically close) if ${max}_{S \subseteq Λ} {| \Pr [X \in S] - \Pr [Y \in S] |} ⩽ ε$ or equivalently $\frac{1}{2} \sum_{x \in Λ} | \Pr [X = x] - \Pr [Y = x] | ⩽ ε$ .

Definition 6.1 (Deterministic randomness extractor).

For any $ε = ε (n) > 0$ , a family of functions $E = {E_{n}}_{n \in N}$ where $E_{n} : Σ^{n} \to Σ^{m (n)}$ is said to be a deterministic ε-extractor for a class of ensemble of distributions $C$ if for every ensemble of distributions $X = {X_{n}}_{n \in N}$ in $C$ , where $X_{n}$ is on $Σ^{n}$ , for all large enough n, the distribution $E_{n} (X_{n})$ is $ε (n)$ -close to $U_{m (n)}$ .

Likewise, a seeded ε-extractor is defined and the only difference is that now it takes a $d (n)$ -bit string chosen according to $U_{d (n)}$ , as an extra input. Before going further, we mention that for ease of presentation, now onwards we will only talk about the definitions and results derived so far related to pseudorandomness and dimension by considering all polynomial size circuits and inverse polynomial bias. We now define the notion of a pseudorandom extractor, the purpose of which is to extract out pseudorandom distribution from a given distribution.

Definition 6.2 (Pseudorandom extractor).

A family of functions $E = {E_{n}}_{n \in N}$ where $E_{n} : Σ^{n} \to Σ^{m (n)}$ is said to be a deterministic pseudorandom extractor for a class of ensemble of distributions $C$ if for every ensemble of distributions $X = {X_{n}}_{n \in N}$ in $C$ , where $X_{n}$ is on $Σ^{n}$ , $E (X)$ is pseudorandom.

A family of functions $E = {E_{n}}_{n \in N}$ where $E_{n} : Σ^{n} \times Σ^{d (n)} \to Σ^{m (n)}$ is said to be a seeded pseudorandom extractor for a class of ensemble of distributions $C$ if for every ensemble of distributions $X = {X_{n}}_{n \in N}$ in $C$ , $E (X, U_{d})$ is pseudorandom.

In this section, we will concentrate on the class of distributions having dimension at least s. It is clear from the results stated in Section 5.2 that this class of distribution is a strict superset of the class of distributions with HILL-type pseudo min-entropy at least $s n$ , for which any randomness extractor will act as a pseudorandom extractor [4]. Thus it is natural to ask the following.

Question 6.3.
For any $s \in (0, 1]$ , does there exist a deterministic/seeded pseudorandom extractor for the class of ensemble of distributions having dimension at least s?

Just like the case of randomness extraction, one can easily argue that deterministic pseudorandom extraction is not possible.10
¹⁰
Suppose $E = {E_{n}}_{n \in N}$ with $E_{n} : Σ^{n} \to Σ$ is a deterministic pseudorandom extractor, then for all n, there exists $x \in Σ$ such that $| E_{n}^{- 1} (x) | ⩾ 2^{n - 1}$ . Thus E is not a pseudorandom extractor for a source D that is a uniform distribution on $E_{n}^{- 1} (x)$ for all n and by Lemma 5.8, $dim (D) ⩾ s$ for any $s < 1$ .

The next natural question is what the lower bound on the seed length will be. We answer this question in the following theorem.
Theorem 6.4.
Suppose for any $s \in (0, 1]$ , $E = {E_{n}}_{n \in N}$ where $E_{n} : Σ^{n} \times Σ^{d (n)} \to Σ^{m (n)}$ be a seeded pseudorandom extractor for the class of ensemble of distributions having dimension at least s and for some $δ > 0$ , $m (n) = {(s n)}^{δ}$ . Then $d (n) = Ω (log n)$ .
Proof.
For the sake of contradiction, let us assume that $d (n) = o (log n)$ . Now by doing a walk according to the output distribution on an odd-length cycle, we achieve the following claim. Claim.
There is a deterministic $\frac{1}{\sqrt[4]{m}}$ -extractor $E^{'} = {E_{m}^{'}}_{m \in N}$ where $E_{m}^{'} : Σ^{m} \to Σ^{\frac{log m}{4}}$ for all pseudorandom ensemble of distributions.

This claim follows from the stronger result stated in Theorem 6.8. Now construct the following function ${Ext}_{n} : Σ^{n} \times Σ^{d (n)} \to Σ^{c log n}$ for some constant $c > 0$ such that ${Ext}_{n} (x, y) = E_{n}^{'} (E_{n} (x, y))$ for all $x \in Σ^{n}, y \in Σ^{d (n)}$ . The function $Ext$ is a seeded $\frac{1}{{(s n)}^{δ / 4}}$ -extractor with $d (n) = o (log n)$ , but it is well known due to [30, Theorem 1.9] that any such randomness extractor must satisfy $d (n) = Ω (log n)$ and hence we get a contradiction. □

However, the question on constructing an explicit or polynomial time computable seeded pseudorandom extractor with seed length $O (log n)$ is still open and next, we formally pose this question.
Question 6.5.
For any $s \in (0, 1]$ , can one construct a seeded pseudorandom extractor $E = {E_{n}}_{n \in N}$ where $E_{n} : Σ^{n} \times Σ^{d (n)} \to Σ^{m (n)}$ in polynomial time, for the class of ensemble of distributions having dimension at least s such that $m (n) = {(s n)}^{δ}$ for some $δ > 0$ and $d (n) = O (log n)$ ?

Note that it is important to consider dimension in the statement of Questions 6.3 and 6.5, because if we consider strong dimension instead of dimension then sometimes it might be just impossible to extract out pseudorandom distributions. For example one can consider the ensemble of distributions mentioned in the proof of Theorem 4.9 where however strong dimension is 1, as for infinitely many n, support of $D_{n}$ contains just a single string, thus one cannot hope to get any pseudorandom distribution out of it. In the next part of this section, we will see a special type of nonpseudorandom source and give an explicit construction of deterministic pseudorandom extractor for that particular type of source. Before proceeding further, we want to mention that it is also very interesting to consider nonpseudorandom distributions samplable by poly-size circuits and we will discuss on the existence of extractor for that particular source in Section 6.2.
6.1. Deterministic pseudorandom extractor for nonpseudorandom bit-fixing sources

In Section 4 while proving Theorem 4.3, we have introduced a special type of nonpseudorandom distribution which looks similar to the $(n, k)$ -bit-fixing source defined as a distribution X over $Σ^{n}$ such that there exists a subset $I = {i_{1}, \dots, i_{k}} \subseteq {1, \dots, n}$ where all the bits at the indices of I are independent and uniformly chosen and rest of the bits are completely fixed. This distribution was introduced by Chor et al. [6]. Now we define an analogous notion for the class of nonpseudorandom distributions, which we term nonpseudorandom bit-fixing sources.

Definition 6.6 (Nonpseudorandom bit-fixing source).

Let $s \in (0, 1)$ . An ensemble of distributions $D = {D_{n}}_{n \in N}$ , where $D_{n}$ is an distribution over $Σ^{n}$ , with dimension s is an $(n, s)$ -nonpseudorandom bit-fixing source if for all n there exists a subset $I = {i_{1}, \dots, i_{⌈ s n ⌉}} \subseteq {1, \dots, n}$ such that all the bits at the indices of I come from a pseudorandom distribution and rest of the bits are fixed.

We devote the rest of the section to achieve an affirmative answer to the question of constructing deterministic pseudorandom extractor for the nonpseudorandom bit-fixing sources. For this purpose, we show that a careful analysis of the technique used in the construction of the deterministic randomness extractor for bit-fixing random sources by Gabizon, Raz and Shaltiel [9] will lead us to the desired deterministic pseudorandom extractor.

Theorem 6.7.
For any $s \in (0, 1]$ , there is an explicit deterministic pseudorandom extractor $E = {E_{n} : Σ^{n} \to Σ^{m (n)}}_{n \in N}$ , for all $(n, s)$ -nonpseudorandom bit-fixing sources having polynomial-size support where $m (n) = {(s n)}^{Ω (1)}$ .

We first extract $O (log s n)$ amount of almost random bits and then use the same as seed in the seeded extractor. To use the seeded extractor, we modify the source such that it becomes independent of the random bits extracted. Before going into the exact details of the proof, we first discuss the ingredients required in the proof of the theorem.
6.1.1. Pseudorandom walk and extracting a few random bits

Kamp and Zuckerman [19] use a technique of random walk on odd-length cycles to extract almost random bits from a bit-fixing source. We adapt this to extract $O (log s n)$ almost random bits from a $(n, s)$ -nonpseudorandom bit-fixing source.

Theorem 6.8.
Let $s \in [0, 1]$ , $k = ⌈ s n ⌉$ . Then there is a deterministic $\frac{1}{\sqrt[4]{k}}$ -extractor $E = {E_{n} : Σ^{n} \to Σ^{\frac{log k}{4}}}_{n \in N}$ for all $(n, s)$ -nonpseudorandom bit-fixing sources.

We prove the above theorem using the property of pseudorandom walk together with the fact that the second largest eigenvalue of a l length odd cycle is $cos (π / l)$ . Note that a corollary of the above theorem is the claim used in the proof of Theorem 6.4. Before proving the above theorem, we state two lemmas required for the proof. The first is a very special case of a lemma given in [19] which was restated in [9].
Lemma 6.9 ([9]).

Let $n \in N$ , $k ⩽ n$ and $s \in [0, 1]$ . Suppose G is an odd length cycle having M vertices and having second largest eigenvalue λ. If we take a walk on G according to the bits from a $(n, k)$ -bit-fixing source, starting from any fixed vertex, then at the end of the n step of the walk, the distribution P on the vertices will be $\frac{1}{2} λ^{k} \sqrt{M}$ -close to $U_{M}$ .

Now we prove a similar result for $(n, s)$ -nonpseudorandom bit-fixing source using the property of pseudorandom walk. The idea of pseudorandom walk was also used previously in the domain of space bounded computation by Reingold et al. [29].

Lemma 6.10.
Let $s \in [0, 1]$ and $k = ⌈ s n ⌉$ . Let G be an odd length cycle having M vertices and having second largest eigenvalue λ. If we take a walk on G according to the bits from a $(n, s)$ -nonpseudorandom bit-fixing source starting from any fixed vertex, then for all large enough n, at the end of the n step of the walk, the distribution Q on the vertices will be $\frac{1}{2} (λ^{k} + \sqrt{M} ε (n)) \sqrt{M}$ -close to $U_{M}$ , where M is polynomial in n and $ε (n) < 1 / n^{c}$ for any constant $c > 0$ .
Proof.
Let π be the stationary distribution on the vertices and since we consider an odd length cycle (a 2-regular graph), the stationary distribution is the uniform distribution on M vertices. Suppose we take a n step walk on the graph G starting from any vertex v according to the bits from a $(n, k)$ -bit-fixing source, where $k = ⌈ s n ⌉$ and the probability vector on the vertices at the end of the walk is $P = (\begin{matrix} p_{1} & p_{2} & \dots & p_{M} \end{matrix})$ . Now we take a n step walk on the graph G starting from the same vertex v according to the bits from a $(n, s)$ -nonpseudorandom bit-fixing source and the probability vector on the vertices at the end of the walk is $Q = (\begin{matrix} q_{1} & q_{2} & \dots & q_{M} \end{matrix})$ , where $\forall_{1 ⩽ i ⩽ M}, q_{i} ⩽ p_{i} + ε (n)$ and $ε (n) < 1 / n^{c}$ for any constant $c > 0$ . This bound on $q_{i}$ can be justified as follows.

Note that the only difference between $(n, s)$ -nonpseudorandom bit-fixing source and $(n, k)$ -bit-fixing source is that on the set I, in $(n, k)$ -bit-fixing source, we have $U_{k}$ instead of pseudorandom distribution (say D) on $Σ^{k}$ . Also observe that actually P and Q are the distributions on vertices at the end of a k step walk, where the walk was started from the vertex v and done according to the bits coming from $U_{k}$ and D respectively, because a step according to a fixed bit will not change the output distribution and in a $(n, k)$ -bit-fixing source (also in a $(n, s)$ -nonpseudorandom bit-fixing source), all the $n - k$ bits are fixed. For a step according to a fixed bit gives rise to a transition matrix that is actually a permutation matrix and thus it leaves the distance from uniform unchanged. Hence, if the bound on $q_{i}, \forall_{1 ⩽ i ⩽ M}$ is not true then we can use this k step walk on G as a polynomial (polynomial in k) time algorithm to distinguish between $U_{k}$ and D. Thus, $\begin{array}{l} ‖ q - π ‖^{2} & = \sum_{i = 1}^{M} {(q_{i} - \frac{1}{M})}^{2} ⩽ \sum_{i = 1}^{M} {(p_{i} + ε (n) - \frac{1}{M})}^{2} \\ = ‖ p - π ‖^{2} + M ε {(n)}^{2} ⩽ λ^{2 k} + M ε {(n)}^{2} ⩽ {(λ^{k} + \sqrt{M} ε (n))}^{2} . \end{array}$ □

The above lemma together with the fact that the second largest eigenvalue of a l length odd cycle is $cos (π / l)$ , implies Theorem 6.8. Proof of Theorem 6.8.
Let us take an odd cycle G with $M = \sqrt[4]{k}$ vertices. The second largest eigenvalue of G is $cos (\frac{π}{\sqrt[4]{k}})$ . Now take a walk starting from a fixed vertex of G according to the bits from $(n, s)$ -nonpseudorandom bit-fixing source and finally output the vertex number of the graph G. Thus we get $\frac{log k}{4}$ bits. From Lemma 6.10, we reach distance $\frac{1}{2} ({(cos (\frac{π}{\sqrt[4]{k}}))}^{k} + \sqrt[8]{k} ε (n)) \sqrt[8]{k}$ from uniform.

By the Taylor expansion of the cosine function, for $0 < x < 1$ , $cos (x) < 1 - \frac{x^{2}}{2} + \frac{x^{4}}{24}$ .

Therefore, ${(cos (\frac{π}{\sqrt[4]{k}}))}^{k} < {(1 - \frac{π^{2}}{4 \sqrt{k}})}^{k} < {({exp}^{- \frac{π^{2}}{4}})}^{\sqrt{k}} < 4^{- \sqrt{k}}$ . Hence, $\frac{1}{2} ({(cos (\frac{π}{\sqrt[4]{k}}))}^{k} + \sqrt[8]{k} ε (n)) \sqrt[8]{k} < \frac{1}{\sqrt[4]{k}}$ . Thus we get distribution of $\frac{log k}{4}$ bit strings which is $\frac{1}{\sqrt[4]{k}}$ -close to uniform in statistical distance. □

6.1.2. Sampling and partitioning with a short seed

Here we restate some of the results on sampling and partitioning used in construction of deterministic extractor for bit-fixing sources from [9]. Let $S \subseteq [n]$ be some subset of size k. Now we consider a process of generating a subset $T \subseteq [n]$ such that $k_{\min} ⩽ | S \cap T | ⩽ k_{\max}$ and this process is known as Sampling.

Definition 6.11.
A function $Samp : Σ^{t} \to P ([n])$ is called a $(n, k, k_{\min}, k_{\max}, δ)$ -sampler if for any subset $S \subseteq [n]$ , where $| S | = k$ , $\Pr_{w \in_{R} U_{t}} [k_{\min} ⩽ | Samp (w) \cap S | ⩽ k_{\max}] ⩾ 1 - δ$ .

Now consider a similar process known as Partitioning, the task of which is to partition $[n]$ into m distinct subsets $T_{1}, T_{2}, \dots, T_{m}$ such that for every $1 ⩽ i ⩽ m$ , $k_{\min} ⩽ | S \cap T_{i} | ⩽ k_{\max}$ .

According to [9], the above two processes can be performed using only a few random bits. Lemma 6.12 ([9]).

For any constant $0 < α < 1$ , there exist constants $c > 0$ , $0 < b < 1$ and $\frac{1}{2} < e < 1$ such that for any $n ⩾ 16$ and $k ⩾ {(log n)}^{c}$ , there is an explicit construction of a function $Samp : Σ^{t} \to P ([n])$ which is a $(n, k, \frac{k^{e}}{2}, 3 k^{e}, O (k^{- b}))$ -sampler, where $t = α log k$ .

Lemma 6.13 ([9]).

For any constant $0 < α < 1$ , there exist constants $c > 0, 0 < b < 1$ and $\frac{1}{2} < e < 1$ such that for any $n ⩾ 16$ and $k ⩾ {(log n)}^{c}$ , there is an explicit construction that uses only $α log k$ random bits and partition $[n]$ into $m = O (k^{b})$ many subsets $T_{1}, T_{2}, \dots, T_{m}$ such that for any subset $S \subseteq [n]$ , where $| S | = k$ , $\Pr [\forall 1 ⩽ i ⩽ m, \frac{k^{e}}{2} ⩽ | T_{i} \cap S | ⩽ 3 k^{e}] ⩾ 1 - O (k^{- b})$ .

6.1.3. Generating an independent seed

In this subsection, we see the way of obtaining a short seed from a nonpseudorandom bit-fixing source so that we can use them in a seeded pseudorandom extractor to extract out almost all the pseudorandom part from the source. The main problem of using this short seed in a seeded pseudorandom extractor is that the already obtained seed is dependent on the main distribution. Now we describe that this problem can be removed in the case of nonpseudorandom bit-fixing sources. Even though the result is analogous to [9], the proofs differ in essential details.

Definition 6.14 (Seed obtainer).

A family of functions $F = {F_{n} : Σ^{n} \to Σ^{n} \times Σ^{d (n)}}_{n \in N}$ is said to be a $(s, s^{'}, ρ)$ -seed obtainer ( $s^{'} ⩽ s$ ) if for every $(n, s)$ -nonpseudorandom bit-fixing source $X = {X_{n}}_{n \in N}$ , the distribution $R = {R_{n} = F_{n} (X_{n})}_{n \in N}$ can be written as $R = η Q + \sum_{a} α_{a} R_{a}$ 11

¹¹
It means for all n, $R_{n} = η (n) Q_{n} + \sum_{a} α_{a} (n) {R_{a}}_{n}$ .

for

η = η (n) > 0

α_{a} = α_{a} (n) > 0

and

η (n) + \sum_{a} α_{a} (n) = 1

such that

η (n) ⩽ ρ (n)

and for every a, there exists a

(n, s^{'})

-nonpseudorandom bit-fixing source

Z_{a}

such that for all large enough n,

{R_{a}}_{n}

ρ (n)

-close to

{Z_{a}}_{n} \otimes U_{d (n)}

In the above definition, by ${Z_{a}}_{n} \otimes U_{d (n)}$ , we mean the product of two distributions ${Z_{a}}_{n}$ and $U_{d (n)}$ . From the above definition it is clear that given a seed obtainer and a seeded pseudorandom extractor for nonpseudorandom bit-fixing sources, we can easily construct a deterministic pseudorandom extractor. The following theorem provides us the details of such construction, where the correctness follows from the properties of our proposed notion of dimension described in Section 4.

Theorem 6.15.

Suppose $F = {F_{n} : Σ^{n} \to Σ^{n} \times Σ^{d (n)}}_{n \in N}$ is a $(s, s^{'}, ρ)$ -seed obtainer, where $ρ (n) ⩽ \frac{1}{{(s n)}^{c}}$ for some constant $c > 0$ and $E^{'} = {E_{n}^{'} : Σ^{n} \times Σ^{d (n)} \to Σ^{m (n)}}_{n \in N}$ is a seeded pseudorandom extractor for $(n, s^{'})$ -nonpseudorandom bit-fixing sources, where $m (n) = {(s n)}^{Ω (1)}$ . Then the function $E = {E_{n} : Σ^{n} \to Σ^{m (n)}}_{n \in N}$ defined as $E_{n} (x) = E_{n}^{'} (F_{n} (x))$ for all $x \in Σ^{n}$ , is a deterministic pseudorandom extractor for $(n, s)$ -nonpseudorandom bit-fixing sources.

Proof.

By the definition of the seed obtainer, we can write $E (X) = η E^{'} (Q) + \sum_{a} α_{a} E^{'} (R_{a}) = η E^{'} (Q) + (1 - η) Y$ , for some ensemble of distributions Y. Now by Lemma 4.5, for all a, $E^{'} (R_{a})$ is pseudorandom and as a consequence, by Lemma 4.6, Y is pseudorandom as well. Then using Lemma 4.5, we can argue that $E (X)$ is also pseudorandom as $η ⩽ \frac{1}{{(s n)}^{c}}$ , for some constant $c > 0$ . □

Now we give an explicit construction of $(s, s^{'}, ρ)$ -seed obtainer, which is crucial in the later part of this paper. To understand the notion of sampler used in the following theorem, the readers may refer to the last subsection.

Theorem 6.16.

Let $Samp = {{Samp}_{n} : Σ^{t (n)} \to P ([n])}_{n \in N}$ where ${Samp}_{n}$ be a $(n, ⌈ s n ⌉, ⌈ s_{1} n ⌉, ⌈ s_{2} n ⌉, δ (n))$ -sampler and $E = {E_{n} : Σ^{n} \to Σ^{m (n)}}_{n \in N}$ with $m (n) > t (n)$ be a deterministic ε-extractor for $(n, s_{1})$ -nonpseudorandom bit-fixing sources, where $ε (n) < 1 / n^{c}$ for any constant $c > 0$ . Then there is an explicit $(s, s^{'}, ρ)$ -seed obtainer $F = {F_{n} : Σ^{n} \to Σ^{n} \times Σ^{d (n)}}_{n \in N}$ , where $d (n) = m (n) - t (n)$ , $s^{'} = s - s_{2}$ , and $ρ (n) = max {ε (n) + δ (n), \sqrt{ε (n)} 2^{t (n) + 1}}$ .

The construction of the seed obtainer is the same as that mentioned in [9], however the proof requires a slightly different argument. Proof.

The construction of F mentioned in the theorem is as follows:

Given $x \in Σ^{n}$ , compute $E_{n} (x)$ . Denote the first $t (n)$ bits of $E_{n} (x)$ by $E_{n}^{1} (x)$ and the last $(m (n) - t (n))$ bits by $E_{n}^{2} (x)$ ;

Compute ${Samp}_{n} (E_{n}^{1} (X))$ and denote it as T;

Let $x^{'} = x_{[n] ∖ T}$ and $y = E_{n}^{2} (x)$ . If $| x^{'} | < n$ , pad it with zeros to get n-bit long string. Now output $x^{'}, y$ .

Note that the above construction is the same as the construction of seed obtainer given in [9]. However, the proof is not the same and more specifically the proof of the next claim differs from that of the similar claim made in [9]. Here, in the proof we use the properties of pseudorandomness and the fact that the distribution under consideration has polynomial-size support.

Let X be a $(n, s)$ -nonpseudorandom bit-fixing source and now consider any large enough n and let I be the set of indices at which the bits are not fixed. For a string $a \in Σ^{t (n)}$ , $T_{a}$ denotes ${Samp}_{n} (a)$ and $T_{a}^{'}$ denotes $[n] ∖ {Samp}_{n} (a)$ . Given a string $x \in Σ^{n}$ , $x_{a}$ denotes $x_{T_{a}}$ and $x_{a}^{'}$ denotes n-bit string obtained by padding $x_{T_{a}^{'}}$ with zeros. Let $X^{'} = X_{E_{n}^{1} (X_{n})}^{'}$ and $Y = E_{n}^{2} (X_{n})$ . We say that a string $a \in Σ^{t (n)}$ correctly splits $X_{n}$ if $⌈ s_{1} n ⌉ ⩽ | I \cap T_{a} | ⩽ ⌈ s_{2} n ⌉$ . Claim.

For every $a \in Σ^{t (n)}$ which correctly splits $X_{n}$ , $(X_{a}^{'}, E_{n} (X_{n}))$ is $ε (n)$ -close to $(X_{a}^{'} \otimes U_{m (n)})$ , where $ε (n) < 1 / n^{c}$ for any constant $c > 0$ .

Proof.

Let $| {Samp}_{n} (a) | = l$ . Given a string $σ \in Σ^{l}$ and a string $σ^{'} \in Σ^{n - l}$ , we define $[σ; σ^{'}]$ as follows:

Suppose l indices of $T_{a}$ are $i_{1} < \dots < i_{l}$ and the $(n - l)$ indices of $T_{a}^{'}$ are $i_{1}^{'} < \dots < i_{n - l}^{'}$ . The string $[σ; σ^{'}] \in Σ^{n}$ is defined as: $\begin{matrix} {[σ; σ^{'}]}_{i} = \{\begin{matrix} σ_{j}, & i \in T_{a} and i_{j} = i, \\ σ_{j}^{'}, & i \in T_{a}^{'} and i_{j}^{'} = i . \end{matrix} \end{matrix}$ In this notation, we denote $X_{n} = [X_{a}; X_{a}^{'}]$ . Now consider the distribution $(X_{a}^{'}, E_{n} (X_{n})) = (X_{a}^{'}, E_{n} ([X_{a}; X_{a}^{'}]))$ . For every $b \in Σ^{n - l}$ , we consider the event ${X_{a}^{'} = b}$ . As a correctly splits $X_{n}$ , there are at least $⌈ s_{1} n ⌉$ “good” indices in $T_{a}$ . Now fix some $b \in Σ^{n - l}$ such that $X_{n} [X_{a}^{'} = b] > 0$ .

Now we claim that for all subsets $B \subseteq Σ^{n - l}$ where $\forall_{b \in B}, X_{n} [X_{a}^{'} = b] > 0$ , there exists a $b^{'} \in B$ such that the distribution $([X_{a}; X_{a}^{'}] | X_{a}^{'} = b^{'})$ forms an $(n, s_{1})$ -nonpseudorandom bit-fixing source if for some constant $c > 0$ , $ε^{'} (n) ⩾ 1 / n^{c}$ and $\begin{matrix} \sum_{b \in B} X_{n} [X_{a}^{'} = b] > ε^{'} (n) . \end{matrix}$

For the sake of contradiction, let us assume that the above claim is not true. It means that there exists a subset $J \subseteq Σ^{n - l}$ , where

$\forall_{b \in J}$ , $X_{n} [X_{a}^{'} = b] > 0$ ,

$\sum_{b \in J} X_{n} [X_{a}^{'} = b] > ε^{'} (n)$ where $ε^{'} (n) ⩾ 1 / n^{c}$ , for some constant $c > 0$ , and also

for all $b \in J$ , the distributions $([X_{a}; X_{a}^{'}] | X_{a}^{'} = b)$ are not forming $(n, s_{1})$ -nonpseudorandom bit-fixing sources.

Now let us consider only the “good” positions which are

⌈ s n ⌉

many in X and at least

⌈ s_{1} n ⌉

many in

([X_{a}; X_{a}^{'}] | X_{a}^{'} = b)

. So the above assumption implies that the ensemble of distributions formed by considering those

⌈ s_{1} n ⌉

bits (this part of the string b is denoted as

b_{⌈ s_{1} n ⌉}

) in

([X_{a}; X_{a}^{'}] | X_{a}^{'} = b)

is not pseudorandom, i.e., it has its corresponding distinguishing circuits

C_{b}

. If this is the case, then the circuit C (by hard-wiring the good random bits) corresponding to the following algorithm A, will act as a distinguishing circuit for the pseudorandom distribution P on

⌈ s n ⌉

many bits; which is a contradiction. The algorithm A is as follows: on input

y \in {0, 1}^{⌈ s_{1} n ⌉}

, if

y_{⌈ s_{1} n ⌉} = b_{⌈ s_{1} n ⌉}

for any

b \in J

, then return

C_{b} (y_{⌈ s_{1} n ⌉})

; otherwise return 0 or 1 uniformly. And thus clearly,

\begin{matrix} | P [A [y] = 1] - U_{⌈ s_{1} n ⌉} [A [y] = 1] | > 1 / n^{c} . \end{matrix}

Circuit C is nothing but the combination of all the circuits $C_{b}$ , for $b \in J$ , each of which is of polynomial size. Now as $\forall_{b \in J}$ , $X_{n} [X_{a}^{'} = b] > 0$ and by our assumption that the distribution under consideration has polynomial-size support (see statement of Theorem 6.7), the support of the subset J is at most polynomial. Hence the circuit C is of polynomial size. Note that this is the only place where we use the fact that the distribution under consideration is of polynomial-size support.

So, we can write, $\begin{array}{l} \frac{1}{2} \sum_{b, c} | \Pr [(X_{a}^{'}, E (X)) = (b, c)] - \Pr_{(X_{a}^{'} \otimes U_{m (n)})} [b, c] | \\ = \frac{1}{2} \sum_{b, c} | \Pr [X_{a}^{'} = b] \Pr [E_{n} (X_{n}) = c | X_{a}^{'} = b] - \Pr [X_{a}^{'} = b] \Pr_{U_{m (n)}} [c] | ⩽ ε (n), \end{array}$ where $ε (n) < 1 / n^{c}$ for any constant $c > 0$ . The first inequality follows from the fact that we can split the sum in two parts one in which $([X_{a}; X_{a}^{'}] | X_{a}^{'} = b)$ ’s are not $(n, s_{1})$ -nonpseudorandom bit-fixing sources and another in which $([X_{a}; X_{a}^{'}] | X_{a}^{'} = b)$ ’s are at least $(n, s_{1})$ -nonpseudorandom bit-fixing sources. □

Next we mention a claim from [9] that makes comment on independence of the pair $(X_{a}^{'}, E_{n}^{2} (X_{n}))$ conditioned on the event $E_{n}^{1} (X_{n}) = a$ . Claim ([9]).

For every fixed $a \in Σ^{t (n)}$ that correctly splits $X_{n}$ , the distribution $((X_{a}^{'}, E_{n}^{2} (X)) ∣ E_{n}^{1} (X) = a)$ is $ε (n) 2^{t + 1}$ -close to $(X_{a}^{'} \otimes U_{m (n) - t (n)})$ .

Note that as a correctly splits $X_{n}$ , so $X_{a}^{'}$ forms a $(n, s - s_{2})$ -nonpseudorandom bit-fixing source.

The rest of the proof follows directly from the proof of correctness of the construction of seed obtainer given in [9] with the following parameters $k = ⌈ s n ⌉, k_{\min} = ⌈ s_{1} n ⌉$ , $k_{\max} = ⌈ s_{2} n ⌉$ . □

6.1.4. A seeded pseudorandom extractor

In this subsection, we discuss about how we can extract ${(s n)}^{Ω (1)}$ many pseudorandom bits using $O (log s n)$ random bits. In the next subsection, we will use this seeded pseudorandom extractor and the techniques discussed in the previous subsections, to construct deterministic extractor. The construction of seeded pseudorandom generator given in the proof of the following theorem is same as that of the seeded randomness extractor given in [9]. However, the analysis is quite different and uses some of the properties of dimension.

Theorem 6.17.
For an $s \in (0, 1)$ and any constant $0 < α < 1$ , there exist constants $c > 0$ , $0 < b < 1$ such that there is an explicit function $E = {E_{n} : Σ^{n} \times Σ^{d (n)} \to Σ^{m (n)}}_{n \in N}$ which acts as a seeded pseudorandom extractor for $(n, s)$ -nonpseudorandom bit-fixing sources with $d (n) = α log s n$ and $m (n) = Ω ({(s n)}^{b})$ .
Proof.
Let X be a $(n, s)$ -nonpseudorandom bit-fixing source and for some large enough n, x be a string sampled by $X_{n}$ . The description of the extractor $E_{n} (x, y)$ is as follows:
According to Lemma 6.13 provided in Section 6.1.2, using y as seed, we obtain a partition of $[n]$ into $m (n) = Ω ({(s n)}^{b})$ many sets $T_{1}, T_{2}, \dots, T_{m (n)}$ with the parameter α;

For $1 ⩽ i ⩽ m (n)$ , compute $z [i] = ⨁_{j \in T_{i}} x [j]$ ;

Output $z = z [1] z [2] \dots z [m (n)]$ .
Let $I \subseteq [n]$ be the set of indices at which the bits are not fixed and let $Z_{n}$ be the distribution of the output strings. We need to show that $Z = {Z_{n}}_{n \in N}$ is pseudorandom.

Let $A_{n}$ be the event ${\forall i, | T_{i} \cap I | \neq 0}$ and $A_{n}^{c} = {\exists i, | T_{i} \cap I | = 0}$ be the complement event. According to Lemma 6.13, $\Pr [A_{n}] ⩾ 1 - O ({(s n)}^{- b})$ . Now we can write the output distribution as $\begin{matrix} Z_{n} = \Pr [A_{n}] (Z_{n} | A_{n}) + \Pr [A_{n}^{c}] (Z_{n} | A_{n}^{c}) \end{matrix}$ and hence due to Lemma 4.5, Z is pseudorandom. □

6.1.5. Deterministic pseudorandom extractor

Now it only remains to combine all the components we discussed so far to build the final deterministic pseudorandom extractor mentioned in Theorem 6.7. We first extract $O (log s n)$ amount of almost random bits by Theorem 6.8 and then use the same as seed in the seeded extractor described in Theorem 6.17. To use the seeded extractor it is required to modify the source such that it becomes independent of the random bits extracted using Theorem 6.8. For that purpose, we use the technique developed in Section 6.1.3 and this concludes the proof of Theorem 6.7.

Proof of Theorem 6.7.
Due to Lemma 6.12, we have a $(n, s n, \frac{{(s n)}^{e}}{2}, 3 {(s n)}^{e}, {(s n)}^{- Ω (1)})$ -sampler ${Samp}_{n} : Σ^{t (n)} \to P ([n])$ , where $t (n) = \frac{log s n}{32}$ and $e > \frac{1}{2}$ . From Theorem 6.8, we have a deterministic $\frac{1}{\sqrt[4]{s^{'} n}}$ -extractor $E^{} = {E_{n}^{} : Σ^{n} \to Σ^{m^{'}}}_{n \in N}$ for $(n, s^{'})$ -nonpseudorandom bit-fixing sources where for all large enough n, $s^{'} n ⩾ \frac{{(s n)}^{e}}{2}$ and $m^{'} (n) = \frac{log s^{'} n}{4}$ . Now we use Theorem 6.16 to get $(s, s^{″}, ρ)$ -seed obtainer $F = {F_{n} : Σ^{n} \to Σ^{n} \times Σ^{m^{'} (n) - t (n)}}_{n \in N}$ where for all large enough n, $s^{″} n ⩾ 3 {(s n)}^{e}$ and $ρ (n) = \frac{1}{{(s n)}^{p}}$ , for some constant p. According to Theorem 6.17, we have a seeded pseudorandom extractor $E^{'} = {E_{n}^{'} : Σ^{n} \times Σ^{d (n)} \to Σ^{m (n)}}_{n \in N}$ with $d (n) = \frac{log s n}{32}$ and $m (n) = {(s n - s^{″} n)}^{Ω (1)}$ for $(n, s - s^{″})$ -nonpseudorandom bit-fixing sources. Since $m^{'} (n) = \frac{log s^{'} n}{4} ⩾ \frac{log s n}{16} = t (n) + d (n)$ , we use F and $E^{'}$ in Theorem 6.15 to construct a deterministic pseudorandom extractor $E = {E_{n} : Σ^{n} \to Σ^{m (n)}}_{n \in N}$ . For a large enough n, $m (n) = {(s n - s^{″} n)}^{Ω (1)} = {(s n)}^{Ω (1)}$ and this completes the proof. □

6.2. Discussion on pseudorandom extractor for nonpseudorandom samplable distributions

Another interesting special kind of source is samplable distributions studied by Trevisan and Vadhan [32]. In a natural way, one can extend the definition of samplable distribution to nonpseudorandom distribution as follows: for any $s \in (0, 1]$ , an ensemble of distributions $D = {D_{n}}_{n \in N}$ is said to be s-nonpseudorandom samplable by circuit of size $S = S (n) > n$ if for all large enough n, there exists a circuit C of size at most $S (n)$ that samples from $D_{n}$ and $dim (D) = s$ . Observe that the negative results for deterministic randomness extractor in case of samplable distributions will also applicable for deterministic pseudorandom extractor in case of s-nonpseudorandom samplable distribution. By Lemma 5.8, if $H_{\infty} (D_{n}) ⩾ n - 1$ for all large enough n, then $dim (D) ⩾ s$ for any $s < 1$ . Now by applying the argument in [32], we get the following.

Theorem 6.18.
Suppose $E = {E_{n} : Σ^{n} \to Σ}_{n \in N}$ is a family of functions computable in time $T (n)$ such that E is a deterministic pseudorandom extractor for ensemble of distributions that are s-nonpseudorandom samplable by circuit of size $S (n)$ for any $s < 1$ . Then there is a language in $DTIME (T (n))$ of circuit complexity at least $Ω (S (n))$ .

The existence of deterministic pseudorandom extractors implies separations between deterministic complexity classes and non-uniform circuit classes that are not yet known. So one might have to consider some complexity theoretic assumptions like in [32] to construct deterministic pseudorandom extractor. However, we do not think construction with such strong assumption like in [32] will be interesting in this case as it is known that certain hardness assumption already leads to a construction of optimal pseudorandom generator (see Section 7). Nevertheless, it is natural to ask the question of constructing explicit extractor using $O (log n)$ amount of extra randomness. We do not know any such result so far, but in the next section we will see that if some distribution is samplable using very few ( $O (log n)$ ) random bits, then it is possible to extract out all the pseudorandom bits using extra $O (log n)$ random bits.
7. Approaching towards $P = BPP$

We now show that if there is an exponential time computable algorithm $G = {G_{n}}_{n \in N}$ with $G_{n} : Σ^{O (log n)} \to Σ^{n}$ where the output distribution has dimension s ( $s > 0$ ), then this will imply $P = BPP$ . We refer to this algorithm G as optimal nonpseudorandom generator. The proof of this is similar to the proof of Theorem 7.4 [26]. We start with some basic definitions.

A pseudorandom generator against a class of circuits is a function which takes a random seed as input and outputs a sequence of bits which is a pseudorandom distribution.

Definition 7.1 (Pseudorandom generators).

A function G is said to be a $l (n)$ -pseudorandom generator if

$G = {G_{n}}_{n \in N}$ with $G_{n} : Σ^{l (n)} \to Σ^{n}$ .

$G_{n}$ is computable in $2^{O (l (n))}$ time.

For sufficiently large n, $G_{n} (U_{l (n)})$ is $(n^{2}, 1 / n)$ -pseudorandom.

Definition 7.2 (Optimal pseudorandom generators).

A function G is said to be an optimal pseudorandom generator if it is an $O (log n)$ -pseudorandom generator.

Nisan and Wigderson [26] showed that there is a connection between pseudorandom generators and hard functions in $EXP$ :

Definition 7.3 (Hard function).

A function $f = {f_{n}}_{n \in N}$ where $f_{n} : Σ^{n} \to Σ$ is $(S, ε)$ -hard for any $S = S (n) > n$ and $ε = ε (n) > 0$ , if for all large enough n, for all circuits C of size at most $O (S (n))$ , $\begin{matrix} U_{n} [C (x) = f_{n} (x)] ⩽ \frac{1}{2} + ε (n) . \end{matrix}$

The following theorem shows that under the assumption of existence of hard function in $EXP$ , optimal pseudorandom generator exists [26].

Theorem 7.4 ([26]).

There exists an optimal pseudorandom generators if and only if there is a language L in $EXP$ and $\exists δ > 0$ such that L is $(2^{δ n}, 1 / 2^{δ n})$ -hard.

The proof of the above theorem is constructive and thus we can explicitly convert optimal pseudorandom generators to the hard function and conversely. However this is still a very strong requirement and later Impagliazzo and Wigderson weakened it.

Theorem 7.5 ([18]).

Suppose there is a language L in $EXP$ and $\exists δ > 0$ such that L on inputs of length n cannot be solved by circuits of size at most $2^{δ n}$ . Then there exists a language $L^{'}$ in $EXP$ and $\exists δ^{'} > 0$ such that $L^{'}$ is $(2^{δ^{'} n}, 1 / 2^{δ^{'} n})$ -hard and as a consequence optimal pseudorandom generator exists.

Now let us state and prove the main result of this section.

Theorem 7.6.

Consider any $s \in (0, 1]$ and $c > 0$ . If there exists an algorithm $G = {G_{n}}_{n \in N}$ where $G_{n} : Σ^{c log n} \to Σ^{n}$ computable in $2^{O (log n)}$ such that $dim ({G_{n} (U_{c log n})}) ⩾ s$ , then $P = BPP$ .

Proof.

Suppose $X : = {G_{n} (U_{c log n})}_{n \in N}$ . If $dim (X) = s > 0$ , then for all large enough n, there must be a subset of indices $S \subseteq {1, 2, \dots, n}$ such that $| S | = log n$ and for any $i \in S$ , loss incurred by any polynomial-size predictor at ith bit position is non-zero or in other words, for any polynomial-size circuit family $C = {C_{n}}_{n \in N}$ , $X [C_{i} (x_{1}, \dots, x_{i - 1}) = x_{i}] < 1$ . Actually one can show a much stronger claim that there exists such a subset S such that $| S | = c \cdot n$ , for some constant $c < 1$ . Otherwise $dim (X) = 0$ . To prove this, suppose $| S | = o (n)$ and thus there exists a predictor π such that for every $w \in Σ^{n}$ , $\begin{matrix} Loss (π, w) = \sum_{i = 1}^{n} loss (π (w [1, \dots, i - 1], w [i])) = \sum_{i \in S} loss (π (w [1, \dots, i - 1], w [i])) . \end{matrix}$ Now as $loss (π (w [1, \dots, i - 1], w [i])) ⩽ 1$ , so for all large enough n, for any $ε < \frac{1}{2}$ , ${LossRate}_{ε} (π, X_{n}) = 0$ . Hence $unpred (X) = 0$ and by Corollary 3.7, $dim (X) = 0$ as well.

Suppose S contains first $log n$ many such indices. Also assume that $S = {i_{1}, i_{2}, \dots, i_{log n}}$ and $i_{1} < i_{2} < \dots < i_{log n}$ . Now we define two languages $L_{0}$ and $L_{1}$ as follows: for $j = 0, 1$ , $\begin{matrix} L_{j} : = {y \in Σ^{log n - 1} | \exists x \in Σ^{n} in the support of G_{n} and x_{S} = j y}, \end{matrix}$ where $j y$ denotes the string generated by concatenating j and y. First of all, note that as $i_{1} \in S$ , none of $L_{0}$ and $L_{1}$ is an empty set. Now clearly either $L_{0}$ or $L_{1}$ is the language that satisfies all the conditions of Theorem 7.5 [18]. Otherwise, there exists a predictor circuit of size at most $2^{δ log n}$ , for some $δ > 0$ , i.e., polynomial in n, by which we can predict $i_{log n} th$ bit position or loss incurred by that predictor at $i_{log n} th$ bit position will be zero implying $i_{log n} \notin S$ which is a contradiction. Thus either $L_{0}$ or $L_{1}$ can be used to construct an optimal pseudorandom generator and that eventually implies $P = BPP$ . □

Footnotes

Acknowledgements

The authors thank Somenath Biswas for helpful discussions and comments. The second author thanks Andrej Bogdanov for suggesting the study of the notion of pseudoentropy. The authors also thank the anonymous reviewers for their helpful comments and suggestions. The second and third author would like to acknowledge the support of Research-I Foundation and the third author would also like to acknowledge the support of the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement n. 616787.

References

Agrawal,

Chakraborty,

Das and

Nandakumar, Dimension, pseudorandomness and extraction of pseudorandomness, in: 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, Bangalore, India, 16–18 December 2015, 2015, pp. 221–235.

K.B.

Athreya,

J.M.

Hitchcock,

J.H.

Lutz and

Mayordomo, Effective strong dimension, algorithmic information, and computational complexity, SIAM Journal on Computing 37 (2007), 671–705. doi:10.1137/S0097539703446912.

K.B.

Athreya and

S.N.

Lahiri, Measure Theory and Probability Theory, Springer Verlag, 2006.

Barak,

Shaltiel and

Wigderson, Computational analogues of entropy, in: RANDOM-APPROX,

Arora,

Jansen,

J.D.P.

Rolim and

Sahai, eds, Lecture Notes in Computer Science, Vol. 2764, Springer, 2003, pp. 200–215.

Blum and

Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. Comput. 13(4) (1984), 850–864. doi:10.1137/0213053.

Chor,

Goldreich,

Håstad,

Freidmann,

Rudich and

Smolensky, The bit extraction problem or t-resilient functions, 1985.

Cover, Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin, Technical Report 12, Stanford University Department of Statistics, 1974.

T.M.

Cover and

J.A.

Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience, 2006.

Gabizon,

Raz and

Shaltiel, Deterministic extractors for bit-fixing sources by obtaining an independent seed, in: Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy, 17–19 October 2004, 2004, pp. 394–403. doi:10.1109/FOCS.2004.21.

10.

Goldreich, The Foundations of Cryptography – Volume 1, Basic Techniques, Cambridge University Press, 2001.

11.

Goldwasser and

Micali, Probabilistic encryption, J. Comput. Syst. Sci. 28(2) (1984), 270–299. doi:10.1016/0022-0000(84)90070-9.

12.

Haitner,

Reingold and

S.P.

Vadhan, Efficiency improvements in constructing pseudorandom generators from one-way functions, in: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010, 2010, pp. 437–446.

13.

Håstad,

Impagliazzo,

L.A.

Levin and

Luby, A pseudorandom generator from any one-way function, SIAM Journal on Computing 28(4) (1999), 1364–1396. doi:10.1137/S0097539793244708.

14.

J.M.

Hitchcock, Fractal dimension and logarithmic loss unpredictability, Theoretical Computer Science 304(1–3) (2003), 431–441. doi:10.1016/S0304-3975(03)00138-5.

15.

J.M.

Hitchcock, Effective Fractal Dimension Bibliography, 2011, http://www.cs.uwyo.edu/~jhitchco/bib/dim.shtml (current April, 2011).

16.

J.M.

Hitchcock, Resource Bounded Measure – Bibliography, http://www.cs.uwyo.edu/~jhitchco/bib/rmb.shtml (current April, 2011).

17.

C.-Y.

Hsiao,

C.-J.

Lu and

Reyzin, Conditional computational entropy, or toward separating pseudoentropy from compressibility, in: Proceedings of the Advances in Cryptology – EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, 20–24 May 2007, 2007, pp. 169–186.

18.

Impagliazzo and

Wigderson, P = BPP unless E has sub-exponential circuits: Derandomizing the xor lemma (preliminary version), in: Proceedings of the 29th STOC, ACM Press, 1996, pp. 220–229.

19.

Kamp and

Zuckerman, Deterministic extractors for bit-fixing sources and exposure-resilient cryptography, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 92–101.

20.

C.-J.

Lu,

Reingold,

S.P.

Vadhan and

Wigderson, Extractors: Optimal up to constant factors, in: STOC,

L.L.

Larmore and

M.X.

Goemans, eds, ACM, 2003, pp. 602–611.

21.

J.H.

Lutz, Gales and the constructive dimension of individual sequences, in: Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, 2000, pp. 902–913, Revised as [22]. doi:10.1007/3-540-45022-X_76.

22.

J.H.

Lutz, The dimensions of individual strings and sequences, Information and Computation 187 (2003), 49–79, Preliminary version appeared as [21]. doi:10.1016/S0890-5401(03)00187-1.

23.

J.H.

Lutz, Dimension in complexity classes, SIAM J. Comput. 32(5) (2003), 1236–1259. doi:10.1137/S0097539701417723.

24.

J.H.

Lutz, A divergence formula for randomness and dimension, Theor. Comput. Sci. 412(1–2) (2011), 166–177. doi:10.1016/j.tcs.2010.09.005.

25.

Nisan and

Ta-Shma, Extracting randomness: A survey and new constructions, J. Comput. Syst. Sci. 58(1) (1999), 148–173. doi:10.1006/jcss.1997.1546.

26.

Nisan and

Wigderson, Hardness vs randomness, J. Comput. Syst. Sci. 49(2) (1994), 149–167. doi:10.1016/S0022-0000(05)80043-1.

27.

Nisan and

Zuckerman, More deterministic simulation in logspace, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, 16–18 May 1993, 1993, pp. 235–244.

28.

Nisan and

Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences 52 (1996), 43–52. doi:10.1006/jcss.1996.0004.

29.

Omer Reingold ,

Trevisan and

Vadhan, Pseudorandom walks on regular digraphs and the rl vs. l problem, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC‘06), 2006, pp. 457–466.

30.

Radhakrishnan and

Ta-Shma, Bounds for dispersers, extractors, and depth-two superconcentrators, SIAM Journal on Discrete Mathematics 13 (2000), 2000. doi:10.1137/S0895480197329508.

31.

Shaltiel, Recent developments in explicit constructions of extractors, Bulletin of the EATCS 77 (2002), 67–95.

32.

Trevisan and

S.P.

Vadhan, Extracting randomness from samplable distributions, in: FOCS, IEEE Computer Society, 2000, pp. 32–42.

33.

S.P.

Vadhan and

C.J.

Zheng, Characterizing pseudoentropy and simplifying pseudorandom generator constructions, in: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19–22 May 2012, 2012, pp. 817–836.

34.

Vollmer, Introduction to Circuit Complexity – A Uniform Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, 1999.

35.

A.C.

Yao, Theory and application of trapdoor functions, in: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS’82, IEEE Computer Society, Washington, DC, USA, 1982, pp. 80–91.

Dimension,pseudorandomness and extraction of pseudorandomness 1

Abstract

Keywords

1. Introduction

2.1. Pseudorandomness

Definition 2.1 (Indistinguishability).

Definition 2.2 (Pseudorandomness).

2 Throughout this paper, we consider S ( n ) > n so that the circuit can at least read the full input.

Definition 2.3 ([22]).

Proposition 2.4 ([22]).

2.4. Defining dimension

Definition 2.9 (Strong dimension).

5.1. Basics of information theory

Definition 5.1 (Shannon entropy).

Proposition 5.2 (Chain rule for Shannon entropy).

Definition 5.3 (KL divergence).

Definition 5.4 (Conditional KL divergence).

Proposition 5.5 (Chain rule for KL divergence).

5.2. High HILL-type pseudo min-entropy implies high dimension

Definition 5.6 (HILL-type pseudo min-entropy).

Definition 5.10 (Conditional pseudo Shannon entropy).

Definition 5.11 (Next-bit pseudo Shannon entropy).

Definition 5.12 (KL-hardness).

Theorem 5.13 ([33]).

Definition 6.1 (Deterministic randomness extractor).

Definition 6.2 (Pseudorandom extractor).

Definition 6.6 (Nonpseudorandom bit-fixing source).

Lemma 6.13 ([9]).

6.1.3. Generating an independent seed

Definition 6.14 (Seed obtainer).

11 It means for all n, R n = η ( n ) Q n + ∑ a α a ( n ) { R a } n .

6.1.4. A seeded pseudorandom extractor

Definition 7.1 (Pseudorandom generators).

Definition 7.2 (Optimal pseudorandom generators).

Definition 7.3 (Hard function).

Theorem 7.4 ([26]).

Theorem 7.5 ([18]).

Footnotes

Acknowledgements

References

²
Throughout this paper, we consider $S (n) > n$ so that the circuit can at least read the full input.

¹¹
It means for all n, $R_{n} = η (n) Q_{n} + \sum_{a} α_{a} (n) {R_{a}}_{n}$ .