One-Way Functions and Polynomial-Time Dimension
Abstract
The theory of randomness in computation has developed around several viewpoints on randomness and information, including statistical tests, compression schemes, betting strategies, and efficiently samplable sources. At the level of computability, several of these viewpoints turn out to be equivalent. A fundamental question is how robust these viewpoints remain when the underlying algorithms are subject to computational resource bounds. This paper studies this question for two polynomial-time notions of information density for infinite binary sequences. Polynomial-time dimension, denoted , quantifies information density using polynomial-time betting strategies called -gales. Polynomial-time Kolmogorov complexity rate, denoted , gives a compression-based notion of polynomial-time information density using polynomial-time descriptions. Hitchcock and Vinodchandran (CCC 2004) showed that for every sequence , and asked whether equality always holds. This question was later also posed by Stull.
Our main result proves a duality between the non-robustness of these polynomial-time information-density notions and the existence of one-way functions. Assuming one-way functions exist, we construct a polynomial-time samplable distribution over infinite sequences such that, with probability , the sampled sequence satisfies by a uniform gap. Conversely, we show that if some polynomial-time samplable distribution yields such an almost-sure uniform separation, then infinitely-often one-way functions exist. Thus, separations between these two polynomial-time information-density notions over efficiently samplable sources lie at the same frontier as one-way functions, with the reverse direction yielding infinitely-often one-way functions. This duality gives a negative answer, assuming one-way functions, to the open question posed by Hitchcock, Vinodchandran, and Stull. Furthermore, we show that there are individual sequences witnessing separations between and , and that the gap can be made arbitrarily close to . We also establish analogous bounds for strong polynomial-time dimension and asymptotic upper polynomial-time Kolmogorov complexity rates. The main technical challenge is to connect finite-length pseudorandomness assumptions with asymptotic information-density measures on infinite sequences. Our proof addresses this by developing several new constructions and arguments involving probabilistic tools such as the Borel–Cantelli lemma, Kolmogorov’s inequality for martingales, and techniques for approximating probabilities of efficiently samplable distributions. The work shows that the question of non-robustness for polynomial-time information-density notions, which is prima facie different from standard questions about randomness, pseudorandomness, and cryptography, is in fact intimately related to the existence of one-way functions.
Keywords and phrases:
Polynomial-time dimension, One-way functions, Resource bounded randomness, Kolmogorov complexity, Polynomial-time martingalesCategory:
RANDOMFunding:
Subin Pulari: Supported by the Basic Research Program at HSE University and this paper was prepared in the framework of this program.Copyright and License:
2012 ACM Subject Classification:
Theory of computation Pseudorandomness and derandomization ; Theory of computation Complexity classes ; Theory of computation Cryptographic primitivesAcknowledgements:
The authors would like to thank CS Bhargav, Laurent Bienvenu, John Hitchcock, Elvira Mayordomo, Jaikumar Radhakrishnan, Mahesh Sreekumar Rajasree, Bruno Bauwens and Marius Zimand for helpful comments and discussions.Editors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
An infinite binary sequence can contain regularity that is exposed in different ways. A statistical test may detect a deviation from randomness, a short description may compress many of its prefixes, or a betting strategy may turn predictable patterns into unbounded capital. These perspectives lead both to qualitative notions of randomness and quantitative measures of how much randomness remains visible to a given computational model.
This paper studies one such measure: polynomial-time dimension. We address the longstanding open question of whether its betting and compression formulations continue to agree. We give a negative answer under the assumption that one-way functions exist. The connection is not limited to deriving separations from cryptographic assumptions: we also prove a converse showing that such separations over efficiently samplable sources imply infinitely-often one-way functions.
Constructive dimension is an algorithmic analogue of classical Hausdorff dimension for individual infinite sequences. It was introduced by Lutz [27] via unfair constructive betting strategies on infinite sequences, called -gales. Intuitively, an -gale reads a sequence bit by bit and repeatedly bets its current capital on the next bit. The parameter controls the payoff rule of the game. When is smaller, the game is less favorable to the gambler, so success requires the gambler to exploit stronger regularities in the sequence. The gale succeeds on a sequence if its capital becomes arbitrarily large along that sequence. The constructive dimension of a sequence is the infimum over all values of for which some constructive -gale succeeds. Thus, constructive dimension is a threshold measure of how difficult it is for constructive betting strategies to extract profit from the sequence.
Lutz [28] and Mayordomo [29] gave an equivalent characterization of constructive dimension of a sequence in terms of the Kolmogorov complexity of its prefixes. Here denotes the length of the shortest program that outputs the finite string . In this formulation, the information density of a sequence is measured by comparing the shortest description lengths of its prefixes with their corresponding lengths. More precisely, this compression view is governed by the lower asymptotic rate of prefix complexity, namely the liminf of , where denotes the first bits of . Prefixes that admit much shorter descriptions indicate lower information density, while prefixes that resist compression indicate higher information density. Thus, for constructive dimension, the betting formulation and the compression formulation define the same notion of information density. These equivalent characterizations establish the robustness of constructive dimension as a mathematical concept. They also provide multiple viewpoints that are useful in different contexts for studying randomness and information density. This leaves a natural robustness problem in the polynomial-time setting: whether the compression characterization continues to match the betting characterization once both are restricted to efficient computation.
Polynomial-time dimension is the analogue of constructive dimension at the level of feasible or polynomial-time computation. As above, there are multiple approaches towards quantifying polynomial-time density of information. The compressibility approach uses the time-bounded Kolmogorov complexity of finite prefixes of infinite sequences. The resulting quantity, denoted , is obtained from the lower asymptotic rate of prefix complexity when the programs producing the prefixes are required to run in polynomial time. In other words, measures the information density that remains after compression is restricted to efficient descriptions. The gambling approach defines polynomial-time dimension, denoted , using polynomial-time betting algorithms known as -gales [27]. Here again, an -gale succeeds if its capital becomes arbitrarily large along the sequence, but now the gale itself must be computable in polynomial time. The value is the infimum over all values of for which some polynomial-time -gale succeeds on . Thus, measures the information density that cannot be exploited away by any polynomial-time betting strategy.
At the levels of polynomial-space computation [16] and finite-state computation [5, 4], these notions are known to be equivalent. At the polynomial-time level, Hitchcock and Vinodchandran proved that is at least as large as . The converse direction has remained open for two decades. This question of robustness of polynomial-time dimension was posed by Hitchcock and Vinodchandran [14, 16], and later mentioned in a survey by Stull (see Open Question 3.71 in [36]).
The positive equivalences at the computability and polynomial-space levels rely on computational power that can effectively search over descriptions or simulate betting strategies. Such conversions are not available at polynomial time. Thus, in the polynomial-time setting, the robustness problem becomes sensitive to the computational limits imposed on the compression and betting algorithms. A related positive characterization is known for polynomial-time dimension when the compression side is formulated using reversible polynomial-time compressors that do not start from scratch [26]. In contrast, the question addressed in this paper concerns the original time-bounded Kolmogorov-complexity formulation of Hitchcock and Vinodchandran.
In this work, we give a surprising negative resolution to this question under the standard cryptographic assumption that one-way functions exist. First, assuming one-way functions, we construct a polynomial-time samplable distribution over for which a set of sequences of -measure exhibits a strict dimension gap between and . We then strengthen this from sets to individual sequences, showing that there are sequences for which under the same assumption. Moreover, the gap can be made arbitrarily close to . The analogous non-robustness also holds for strong polynomial-time dimension, where lower asymptotic rates are replaced by upper asymptotic rates.
We also prove a partial converse: the existence of a polynomial-time samplable distribution supporting such dimension gaps implies the existence of infinitely-often one-way functions. This shows that the connection is not limited to deriving dimension gaps from cryptographic assumptions. Via the converse implication, dimension gaps over efficiently samplable sources lead to infinitely-often one-way functions.
Formally connecting one-way functions to the failure of robustness for these asymptotic measures of randomness requires arguments tailored to infinite sequences. The classical connections between compressibility, indistinguishability, and pseudorandomness in the finite-string setting [17, 38, 21] do not by themselves control information rates along infinitely many prefixes, or the success of a betting strategy along an infinite sequence.
The forward implication has to pass from asymptotic betting success on infinite sequences to finite-length distinguishers. A key step is an argument involving the Borel–Cantelli lemma, which isolates infinitely many lengths where the constructed source produces prefixes on which the betting strategy has substantial gain. This is paired with a martingale estimate based on Kolmogorov’s inequality, showing that comparable gains are unlikely under uniform randomness. The separation between these two behaviors is then turned into a pseudorandomness distinguisher.
The converse direction is technically different. Here the task is to show that an almost-sure dimension gap over an efficiently samplable source already carries cryptographic content. Assuming that infinitely-often one-way functions do not exist, one can approximate the probabilities of samplable distributions on typical inputs. The proof has to assemble these finite-prefix approximations into an efficient betting algorithm that works along the infinite sequence. This converts the absence of cryptographic hardness into a robustness statement for polynomial-time information density, and hence forces any such dimension gap to imply infinitely-often one-way functions.
In addition to resolving a longstanding open problem under the assumption that one-way functions exist, our results show that the robustness of polynomial-time information density is not merely a technical question internal to resource-bounded dimension. It is governed by the same phenomenon that underlies modern cryptography: the existence of efficiently samplable objects whose structure cannot be uniformly exposed by feasible computation. Thus the paper establishes a direct bridge between one-way functions and asymptotic information measures.
2 Background: Betting and Compression
Notation.
Let denote the binary alphabet . denotes the set of -length strings and denotes the set of all finite strings over . For a finite string , denotes the length of . denotes the set of all finite strings in the unary alphabet . denotes the Cantor space, or the set of all infinite strings over . We use small letters , to represent finite strings and capital letters , to represent infinite strings over . For an infinite string , denotes the th bit of and denotes the first n bits of . For infinite string and , denotes the the substring . For a finite string , , and are defined similarly. denotes the empty string. denotes the set of natural numbers and denotes the set of rationals. All the logarithms in the paper are taken to base unless specified otherwise. For any function and let denote .
For , denotes the cylinder set of , that is the set of all infinite sequences in that begin with . Let denote the Borel -algebra over generated by the set of all cylinder sets . For two finite strings , denotes the concatenation of the strings and .
We use to denote the set of polynomial (time) functions . When the context is clear, we also use to denote . We use to denote the uniform probability distribution over .
2.1 -gales and Kolmogorov Complexity
-gales are real-valued betting strategies on infinite sequences. An -gale may be viewed as a gambler that reads a sequence bit by bit and repeatedly reallocates its current capital between the two possible next bits. The gale starts with initial capital on the empty string. At the th stage, after seeing a prefix , the gale has capital and places a bet on the next bit . The rule of the game is that, for every finite string , the capital assigned to the two possible extensions satisfies . A gale succeeds on the sequence if it can make its capital arbitrarily large along the sequence, more precisely if .
Definition 1 ([27, 28]).
For , an -supergale is a function such that and for every finite string , . An -gale is a function with for every finite string , . A supermartingale is a -supergale. A martingale is a -gale.
Unless specified otherwise, for every -supergale , we assume that the initial capital .
Definition 2 ([27, 28],[1]).
The success set of an -supergale is . The strong success set of an -supergale is .
For example, fix . The strategy that always bets all its capital on the next bit being is given by , , and . This satisfies the -gale condition. Along the sequence , its capital after steps is , and hence it succeeds. On the other hand, a single bit makes the capital drop to .
A more interesting example is obtained by betting according to a fixed bias. Let , and define
where and are the numbers of zeros and ones in . Then , so is an -gale. If a sequence has limiting frequency of zeros and of ones, then along its prefixes the exponential growth rate of this capital is , where is the binary entropy. Thus, for every , this gale succeeds on such a biased sequence. This example illustrates how an -gale can exploit statistical regularity rather than merely a fixed deterministic pattern.
When , the average capital after betting on or is equal to the previous capital . In this case the betting strategy is fair, and such -gales are precisely martingales. When , the average capital after the bet is strictly smaller than . Thus the gambler is playing in an unfavorable market. This is often interpreted as “betting under inflation”: unless the gambler detects structure in the sequence and bets accordingly, its capital tends to shrink. As decreases, success requires increasingly strong regularities in the sequence.
The Kolmogorov complexity of a finite string , denoted by , is the length of the shortest program that outputs . That is, , where is a program and is the universal Turing machine. Any string can be produced by a program that simply prints , and therefore . However, if the string contains regularity, there may be a much shorter program that outputs it. For instance, if all the even bits of the string are , then the program only needs to encode the bits at the odd indices and insert zeros in the even positions. In that case, is at most about half the length of the string, up to additive constants.
Definition 3 (-time-bounded Kolmogorov complexity [22, 24]).
Let be a time-constructible function, and be a finite binary string. The -time bounded Kolmogorov complexity of is , where is any fixed efficient universal Turing machine.
Since in the study of resource-bounded dimension we divide by , our results are unaffected by the choice between prefix-free Kolmogorov complexity and plain Kolmogorov complexity. We use plain Kolmogorov complexity in the rest of the paper.
2.2 Polynomial-time Dimension
Resource-bounded dimension is defined by placing resource bounds on the computation of the -gale. Analogously, resource-bounded Kolmogorov complexity is defined by placing resource bounds on the programs that print a string. Polynomial-time dimension quantifies the rate of information in an infinite sequence, measured with respect to polynomial-time bounded computation. It is formulated using polynomial-time -gales. An -gale wins on an infinite sequence if . The gale is said to be polynomial-time computable if, for some , the value can be computed in at most time, where is the length of . Intuitively, is the infimum of the values of for which there exists a polynomial-time -gale that succeeds on . Smaller values of correspond to a more unfavorable betting environment. Thus, a low polynomial-time dimension means that some efficient betting strategy can exploit substantial regularity in the sequence, whereas high polynomial-time dimension means that the sequence resists such efficient betting.
On the other hand, in the incompressibility approach, we use the time-bounded Kolmogorov complexity to define a polynomial-time analogue of . For a given time bound , the -time bounded Kolmogorov complexity of a string is the length of the shortest program that generates in at most time steps (see [24]).
For a given time bound , the quantity gives the asymptotic -time-bounded rate of information in an infinite string . The polynomial-time analogue of is the infimum of this quantity over all polynomial-time bounds .
Now, we define the asymptotic polynomial-time density of information of a subset .
For individual sequences, we define and . Note that and are equivalently defined in the following way.
Now, we define time-bounded supergales. We first define -time computable -gales.
Definition 6 (-time computability [27]).
An -supergale is -time computable if there exist a -time computable function such that for every and .
Another notion of time-bounded computability is that of exact -time computability.
Definition 7 (Exact -time computability [27]).
An -supergale is exact -time computable if there exist a -time computable function such that for every .
Now, we define polynomial-time dimension and strong dimension.
Definition 8 (Polynomial-time dimension [27] and strong dimension [1, 36]).
The polynomial-time dimension of is
defined as
For a sequence , define . The polynomial-time strong dimension of is defined by replacing by in the above expression. For a sequence , define .
We now make an important remark. Polynomial-time dimension and strong dimension are often defined in terms of -time computable -gales that need not be exact computable. But these definitions are in fact equivalent. This is a direct consequence of the following lemma from [27] which is also useful in proving the main results in this paper.
Lemma 9 (Exact Computation Lemma [27]).
If there is a polynomial-time computable -gale such that , then there exists an exact polynomial-time computable -gale such that .
We will often use the terminology polynomial-time computable gales to refer to exact -time computable -gales where . Similar comment applies in the case of exact polynomial-time computability and other notions related to gales such as martingales and supergales.
2.3 Robustness of Dimension
At the computability level, the relevant notions are , defined using time-unbounded Kolmogorov complexity , and , defined using lower semicomputable -gales. Lutz [28] and Mayordomo [29] showed that the unbounded notions of and are equivalent, hence establishing the robustness of constructive dimension.
analogues of and are defined by restricting the -gales in the definition of to be polynomial-space computable and by using polynomial-space bounded Kolmogorov complexity in the definition of . Hitchcock and Vinodchandran [14, 16] showed that these notions of resource-bounded dimension coincide in the setting. Thus polynomial-space dimension is robust in the same sense.
This leads to the following question: Are the notions of polynomial-time dimension formulated using -gales () and time-bounded Kolmogorov complexity () equivalent? Hitchcock and Vinodchandran [16] showed that is always greater than or equal to .
The question whether the reverse inequality holds has remained elusive. Hitchcock and Vinodchandran [14, 16] and later Stull in [36] posed the following open question:
Polynomial-time strong dimension is a dual notion of polynomial-time dimension [1, 36]. As in the case of polynomial-time dimension, there exist two notions, one defined using -gales and the other defined in terms of time-bounded Kolmogorov complexity. An -gale strongly succeeds on an infinite sequence if .
The strong dimension analogue of is defined by replacing the in the definition of with . The analogue of Theorem 10 also holds in this setting: is at least as large as . Stull in [36] posed the following question for the dual notion of strong dimension:
Question 12.
Are the notions of polynomial-time strong dimension formulated using -gales () and time-bounded Kolmogorov complexity () equivalent for every sequence ?
We answer both questions in the negative, under the standard cryptographic assumption that one-way functions exist.
2.4 Measure over Cantor Space
Definition 13 ( [34]).
A function , where , is called a measure over if and is countably additive. That is, for any countable disjoint collection of measurable sets,
We take as the set of Borel Measurable sets. Note that , where is the Borel sigma algebra over , we omit and say that is a measure over .
Definition 14.
Let be a measure over . We say that is a probability distribution over if it holds that .
Let be a probability distribution over . For every , let denote the probability distribution induced by on defined as for every .
2.5 One-way Functions and Pseudorandom Generators
One-way functions [6, 10, 23] are functions that are easy to compute but are hard to invert, except possibly on a negligible fraction of inputs. They are central in cryptography, since their existence is necessary for that of essential cryptographic primitives [17, 33, 12, 8, 30].
The following is the definition of one-way functions secure against uniform probabilistic polynomial-time adversaries.
Definition 15 (One-way functions [11, 37, 10]).
A function is a one-way function (OWF) if there is a constant such that is computable in time for sufficiently large , and for every probabilistic polynomial-time algorithm and every constant , , for all sufficiently large , where the probability is taken over the choice of and the internal randomness of algorithm .
To define pseudorandom generators, we first define computational indistinguishability.
Definition 16 (Computational Indistinguishability [11, 37]).
The ensembles of random variables and are computationally indistinguishable if for every probabilistic polynomial-time algorithm and every constant ,
where the probabilities are taken over the distributions of either or and the internal randomness of the algorithm .
Definition 17 (Pseudorandom generators [11, 37, 10]).
A sequence of functions is a pseudorandom generator (PRG) if for all , there exists a uniform deterministic polynomial-time algorithm such that , and the ensembles and are computationally indistinguishable.
The theorem below states the equivalence of one-way functions and pseudorandom generators.
2.6 Efficiently Samplable Sources and Approximable Gales
We generalize the notion of polynomial-time samplable distributions [3] to probability distributions on the space of infinite sequences. This is the distributional setting in which our main duality theorem is stated: instead of considering arbitrary sequences alone, we also study typical outputs of efficiently samplable sources over .
Let be a probability measure over . For every , let 111 denotes the prefix operator denote the probability distribution induced by on . Now, we define polynomial-time samplable distributions on .
Definition 19.
A probability distribution over is polynomial-time samplable if there exists a probabilistic Turing machine that uses random bits, where is a polynomial, such that for every and , .
An alternate way of defining polynomial-time samplable distributions on is the following: is a polynomial-time samplable distribution on if is a polynomial-time samplable distribution ( [3]) such that for any , . The equivalence of these notions follows using routine measure theoretic arguments.
Primitives like one-way functions and pseudorandom generators are defined against probabilistic polynomial-time adversaries, whereas polynomial-time -gales are deterministic betting strategies. To compare these two kinds of objects, we use a mild average-case evaluation notion for gales. The betting strategy itself remains a deterministic -supergale, with the usual success condition along infinite sequences. The relaxation is only in how its capital function is accessed: on inputs drawn from the target samplable distribution, the capital is required to have an efficient randomized constant-factor approximation with high probability.
This is the natural interface for our distributional arguments. On the cryptographic side, pseudorandomness and probability-estimation results are inherently probabilistic and average-case over samples from a samplable distribution. On the dimension side, the object being analyzed is still a gale. Exact polynomial-time computable gales are included as a special case, since their values can be returned deterministically. Thus the notion below does not replace polynomial-time dimension. It is a technical strengthening used to formulate the almost-sure distributional separation and its converse.
This is in the spirit of the probabilistic approximation notions for martingales studied by Regan and Sivakumar [32], but we only need an inverse-polynomial average-case guarantee over : for each length and every constant , the estimator approximates within a fixed constant factor on all but an fraction of samples , and any approximation errors are allowed only on strings in support of .
Definition 20.
Let be an -supergale and be any probability distribution over . is -time -approximable if for every constant there exist a probabilistic -time machine and constant such that for every , and .
Here . The support condition prevents the approximation procedure from hiding errors on impossible prefixes. Equivalently, outside the support of the sampled prefix distribution, the estimator must still output a value within the specified multiplicative range, while on typical samples from the source it may fail only with inverse-polynomial probability.
3 Our Results
3.1 One-way functions and dimension gaps
Our main result gives a two-sided connection between one-way functions and dimension gaps over efficiently samplable sources. Assuming one-way functions, we construct a polynomial-time samplable distribution over whose typical sequences have low polynomial-time Kolmogorov complexity rate but cannot be captured by low-dimensional polynomial-time betting strategies. Conversely, the existence of such a samplable source already implies infinitely-often one-way functions.
Theorem 21.
Item (2a) says that, with -probability , the sampled sequence has small polynomial-time Kolmogorov complexity rate. In particular, for -almost every . The second part of Item (2) rules out success by low-dimensional polynomial-time -approximable supergales. Lemma 42 shows that, under the same assumption, this yields for -almost every . Since , this gives an almost-sure dimension gap over the samplable source.
It is important that the approximation notion in Item (2b) does not change the polynomial-time dimension appearing in the applications below. Every exact polynomial-time computable gale is polynomial-time -approximable, by returning its value deterministically. Thus Item (2b) rules out, in particular, ordinary polynomial-time betting strategies on positive-measure subsets of the samplable source. The approximability condition is used only to state the distributional theorem in a form compatible with pseudorandomness arguments and average-case probability-estimation results.
We prove Theorem 21 in two steps. First we show that one-way functions yield a polynomial-time samplable distribution exhibiting an almost-everywhere dimension gap between and (Lemma 25, giving (1)(2)), and then we show that the existence of such a dimension-gap distribution yields infinitely-often one-way functions (Lemma 36, giving (2)(3)).
3.2 Applications
Theorem 21 resolves the original robustness question for individual sequences, assuming one-way functions.
Theorem 22.
If for all , , then no one-way functions exist.
Equivalently, assuming one-way functions, there are individual sequences such that . We extend this result to show that if one-way functions exist, then the distance between these quantities can be arbitrarily close to the maximum possible value of .
Theorem 23.
If one-way functions exist, then for any , there exists such that .
For polynomial-time strong dimension, we show that if one-way functions exist, then there exist sequences for which the gap between and is arbitrarily close to .
Theorem 24.
If one-way functions exist, then for any , there exists such that .
Therefore, we show that if one-way functions exist, the answers to both parts of Open Question 3.71 from [36] are negative.
4 Proof Outline and Techniques
In this section we describe the main constructions and reductions behind our results. The emphasis is on how finite-length pseudorandomness arguments interact with asymptotic information-density notions over infinite sequences.
The main difficulty is that the two sides are formally quite different. Pseudorandomness is a finite-length indistinguishability notion against probabilistic polynomial-time tests, while dimension is an asymptotic notion defined by success of betting strategies along infinitely many prefixes of one sequence. The proof has to convert information in both directions: from asymptotic betting success to finite distinguishers, and from average-case probability estimation for samplable distributions to betting objects on infinite sequences.
4.1 From one-way functions to dimension gaps
We first show how one-way functions, through pseudorandom generators, yield efficiently samplable sources with an almost-everywhere dimension gap. Concretely, assuming one-way functions, for every we construct a polynomial-time samplable distribution over such that (i) for -almost every , and (ii) for every , no polynomial-time -approximable -supergale succeeds on a set of positive -measure.
Lemma 25.
If one-way functions exist, then for every , there exist a polynomial-time samplable distribution over such that:
-
1.
for almost every .
-
2.
For every and any polynomial-time -approximable -supergale ,.
Fix . Assume one-way functions exist, and choose a dyadic parameter with . Then there are pseudorandom generators running in time with constant stretch: for each , . The choice of such an will give the stronger compression bound needed to obtain .
4.1.1 Construction of the PRG-induced source
We extend the family to a mapping on infinite sequences, , by applying the appropriate blockwise to successive blocks of the input. Given a PRG where for some , we construct a mapping from the Cantor set to itself, by using the family to map blocks within the input string to longer blocks within the output string. Given an input , is constructed by applying to successive blocks of size from for all . We first define a sequence of mappings from to . These mappings preserve the prefix ordering among finite strings and hence we define for as the limit of .
Definition 26.
Let where for some and let . For , define as follows. For any satisfying any and , let , where . For , we set .
Note that . For , maps any to . Observe that the sequence of mappings preserves the prefix order between strings. That is, If , then . Therefore, we define as the limit of the mappings as .
Definition 27.
For every let .
Notice that for any and , . For convenience, we abuse the notation and use to denote the mapping between infinite strings defined above or a mapping between finite strings defined as follows: for any . The intended meaning is clear from the context.
The mapping induces a polynomial-time samplable distribution over . The sampling algorithm for on input maps a random seed of length using to a string of length , and thereafter trims the output to bits. The number of random bits used by on input is at most . Intuitively, because the sampler uses at most random bits on input , those random bits, together with a fixed -bit description of the sampler, provide a short polynomial-time description of the output prefix. Thus, for -a.e. , we obtain . The formal complexity bound is given by the following lemma and corollary.
Lemma 28.
For for some , let be a PRG that runs in time . Let be the function constructed from as in Definition 26. There exists a constant such that for all and for all , , where .
Proof.
Consider the algorithm which implements the mapping in Definition 26 as follows.
Since runs in time, it follows that runs in time. Also, for any and , outputs the string on input . Therefore, it follows that where the constant depends only on the length of any representation of in the prefix language of the fixed universal Turing machine.
We obtain the following corollary.
Corollary 29.
For for some , let be a PRG that runs in time . Let be the function constructed from as in Definition 26. There exists a constant such that for all and for all , , where .
Proof.
From Lemma 28, . With extra bits, we specify the index at which needs to be trimmed. Thus, we obtain a program that outputs in -time. There is a trivial prefix-free program which given bits of information, runs in linear time and prints . Hence, the value of . Since , there exists such that .
4.1.2 From betting gains to a finite-length distinguisher
Suppose toward a contradiction that there exist and a polynomial-time -approximable -supergale with . Since , this is in particular a gale exponent above the compression rate obtained from the PRG-induced source. Using standard gale manipulations, we convert into a polynomial-time -approximable supermartingale that exhibits large multiplicative gains between dyadic checkpoints and infinitely often along every sequence in some positive--measure set. This conversion is carried out in two stages, established in the following lemmas.
Lemma 30.
For if is a -time computable -approximable -supergale, then for any satisfying and , there exists an exact -time -approximable supermartingale such that for any ,
Proof.
Let such that . We know that is a -time -approximable -supergale that succeeds on (see Observation 4.4 from [27]). Let be defined as . Note that as is -approximable, it follows that is -approximable.
From Observation 3.2 in [28], it follows that is a supermartingale such that,
Since is rational, so is . Hence, is an -time -approximable supermartingale.
Lemma 31.
For , let be an -time -approximable -supergale. Let be such that , . Then, there exists an -time -approximable supermartingale such that for any , there exists infinitely many such that
Proof.
Choose such that and . Let be the -time -approximable supermartingale from Lemma 30 such that
Suppose, toward a contradiction, that for some and every ,
Then, for any and ,
If also , then rearranging gives
Since , we obtain
| (1) |
If there are infinitely many such that , then (1) holds for infinitely many . But this is impossible for all large enough , since . Therefore, for infinitely many ,
as required.
Let be a polynomial-time -approximator for . We then define a polynomial-time algorithm that, on input length , samples a random , forms the corresponding prefix , and checks via whether appending the input causes to jump by the required multiplicative factor.
4.1.3 The distinguisher algorithm
Let be the -time -approximable martingale obtained from Lemma 31. Let be the Turing machine that -approximates . That is for all , where are constants such that and . We use to build a distinguisher algorithm that breaks the PRG .
4.1.4 Performance on PRG outputs
A remaining subtlety is that the martingale guarantee is only infinitely often along each sequence in a positive-measure set. We upgrade this to a noticeable fraction at infinitely many lengths using a Borel–Cantelli argument, which yields infinitely many for which a polynomially-large set of seeds witnesses the required dyadic-block gain. At these lengths, the -approximation property of ensures that outputs with inverse-polynomial probability on PRG outputs.
We first define the function such that if has a sufficiently large gain in the -th block of , and otherwise.
Definition 32.
Let be defined by specifying if and 0 otherwise.
The following fact is a consequence of the Borel Cantelli Lemma [2].
Lemma 33.
Let and such that . If for every , there exist infinitely many such that , then for any , there exist infinitely many , such that .
Now, we apply the above lemma to the martingale from Lemma 30 to obtain the following. Recall that was defined at the start of this section as the distribution obtained by applying to random seeds.
Lemma 34.
Given , if for all sequences where , there exists infinitely many such that , then it holds that for infinitely many ,
| (2) |
This follows directly from Lemma 33. Indeed, by the hypothesis and the definition of , every satisfies for infinitely many . Since , Lemma 33 implies that this event has -measure at least for infinitely many , for every . Unwinding the definition of and using that is induced by applying to uniformly random seeds gives the displayed probability bound; taking completes the proof.
Now we analyze the performance of the algorithm on outputs of the PRG. Let be one of the lengths at which the condition in Lemma 34 holds. Let such that for some and for some .
In order for the condition to hold, it suffices that and and .
From Lemma 34, it follows that the first condition holds with probability at least among selected uniformly at random from and taking . Since is -approximable, for some , on input , the computations of all in Algorithm 2 outputs a value in with probability at least according to the distribution . Note that the distribution according to corresponds to applied to the uniform distribution on .
Therefore it follows that for infinitely many n,
Hence, taking , for infinitely many ,
| (3) |
4.1.5 Performance on uniformly random inputs
Finally, we show that outputs with exponentially small probability on a uniformly random input of the same length. This uses the Kolmogorov inequality for supermartingales to bound how many extensions can force a multiplicative jump of the required size, together with the fact that fails to approximate only on a -small set.
Lemma 35 (Kolmogorov Inequality [27]).
Let be a supermartingale. For any and , the number of strings such that for some is less than or equal to .
We need an upper bound on the number of strings and such that . This happens when .
For any , take any , and let . Using the Kolmogorov Inequality for Martingales (Lemma 35), the number of strings such that is less than .
For the remaining set of strings, we have that . If we have that and , it follows that .
We know that, for some . From this, it follows that .
Notice that for every . From the block-wise definition of the mapping , for any fixed , we obtain that there are at most strings in the set contained in . Therefore, for any fixed , the number of strings such that is at most . Therefore, we have that
Therefore, it follows that for any ,
Comparing the two cases yields that for infinitely many lengths, distinguishes PRG outputs from uniform with non-negligible advantage, contradicting pseudorandomness. Hence for every polynomial-time -approximable -supergale with .
4.1.6 Proof of Lemma 25
Proof.
If one-way functions exist then there exists PRG running in time [Theorem 18]. Using , we construct a polynomial-time samplable distribution over as above. By Corollary 29 and the choice of , we have for almost every .
From the arguments in Sections 4.1.4 and 4.1.5, we obtain the following consequence. Suppose there exists some and a polynomial-time -approximable -supergale such that . Then there exists a distinguisher algorithm running in time such that, for infinitely many and for all ,
Let be any constant such that and for all large enough ,
It follows that is not a PRG for infinitely many . Therefore the family is not a PRG, contradicting the assumption that one-way functions exist. This completes the proof of the lemma.
4.2 Infinitely-often one-way functions from dimension gaps
We now explain the reverse direction: an almost-everywhere dimension gap over an efficiently samplable source can be converted into infinitely-often one-way functions.
Lemma 36.
If there exist an and a polynomial-time samplable distribution over such that:
-
1.
for -almost every .
-
2.
There exists such that for every and every polynomial-time -approximable -supergale , we have .
Then infinitely-often one-way functions exist.
Proof.
Assume the hypothesis, and toward a contradiction assume that infinitely-often one-way functions do not exist. Fix reals with , and define
It is straightforward that is an -supergale. The low- condition implies that with -probability close to , draws have many prefixes with small time-bounded description length (say for all large ). For each , there are at most such “typical” strings of length . If all these typical strings had -mass for all large , then the total -mass of typical length- strings would be at most , contradicting that typical strings carry almost all the mass. Therefore, with positive -probability, infinitely many satisfy , and along those we have ; hence .
We now formalize the positive-measure conclusion used above.
Lemma 37.
Notice that if then . Therefore from Lemma 37 we obtain that
On the other hand, under the assumption that infinitely-often one-way functions do not exist, we invoke a distributional estimation theorem for polynomial-time samplable distributions. Distributional estimation results of this kind go back to Impagliazzo and Luby [20] and Impagliazzo and Levin [19]. Ilango, Ren, and Santhanam [18] give an algorithm that, for every polynomial-time samplable distribution ensemble , estimates within a constant multiplicative factor on all but a -small exceptional set of samples . Nanashima and Hirahara [13] prove a substantially stronger form, giving a multiplicative approximation (for arbitrarily small ) on almost all samples from . Such distributional estimation results can be used to obtain efficient algorithms for universal extrapolation and Solomonoff’s inductive inference. For our purposes in this paper, the constant-factor guarantee from [18] is sufficient, and we apply it to the particular samplable distribution . Combining this estimator with a standard gale normalization step yields a polynomial-time -approximator for on , and therefore for (using ). Thus is a polynomial-time -approximable -supergale with , contradicting item (2). Hence infinitely-often one-way functions must exist. The formal estimation result and the approximability argument are given next.
Theorem 38 ([18, 20, 19, 13]).
Assume that no infinitely-often one-way functions exist. Let be a polynomial-time samplable distribution and be an arbitrary constant. Then, there exists a probabilistic polynomial-time algorithm and constant such that for all ,
Claim 39.
is polynomial-time -approximable.
Proof.
Let be the machine that samples the distribution such that for every , for every . Let be the constant such that uses random bits to sample a string of length .
Assume that no infinitely-often one-way functions exist. Then, the function defined as
is not an infinitely-often weak one-way function. Hence for any there exist an algorithm such that for all ,
| (4) |
From our assumption that infinitely-often one-way functions do not exist and Theorem 38, we obtain that for any , there exists a probabilistic polynomial-time algorithm and constant such that for all ,
| (5) |
Finally, we give the algorithm that -approximates . on input runs on . If , outputs . Else, runs on and outputs . Since , runs in polynomial time. For any such that (i.e. ), will never succeed in finding a pre-image such that and hence always outputs . Therefore for every , . Now, from (4) and (5) we obtain that,
Therefore for every , . Since runs in randomized polynomial time and is arbitrary, witnesses the fact that is a polynomial-time -approximable -gale.
The claim shows that is a polynomial-time -approximable -supergale. Since and , this contradicts the second item in the hypothesis. Therefore, infinitely-often one-way functions exist.
4.3 Dimension gaps over sequences from one-way functions
Lemma 25 is a measure statement: under one-way functions it gives a samplable distribution on for which typical sequences have low , but every polynomial-time -approximable gale of exponent succeeds only on a -null set. We now indicate how this measure-theoretic gap yields an individual sequence with small but bounded away from it, and then how the same strategy can be pushed to obtain gaps arbitrarily close to .
Theorem 22. [Restated, see original statement.]
If for all , , then no one-way functions exist.
We first record the gale-combination construction needed to pass from pointwise polynomial-time gales, whose running-time exponents may vary with the sequence, to a single polynomial-time gale on a positive-measure set.
Lemma 40.
For any time , and with , there exists an exact -time computable -gale such that for all exact -time computable -gales , there exist a constant such that for all and , .
Theorem 41.
If one-way functions exist, then for every , there exist such that and .
Proof.
Assume that one-way functions exist. From the proof of Lemma 25, we obtain that for every there exist a polynomial-time samplable distribution over and polynomial such that:
-
1.
The number of random bits used by the sampler for on input is at most .
-
2.
For every and any polynomial-time -approximable -supergale ,.
Consider the canonical closed full-measure support set Now, is a finite union of cylinder sets in and hence is a closed set. Since is a polynomial-time samplable probability distribution on , is a superset of for every . Since is an intersection of a decreasing sequence of non-empty closed sets in the compact space , is non-empty (see [35]). Since for every , using the continuity of probability measures from above [2], we get . Since the number of random bits used by the sampler for on input is at most , for every .
For the sake of contradiction, assume that there exists such that for every . So, for every there exists an exact computable -gale that runs in time , such that succeeds on . We group according to a polynomial running-time exponent. Define
and let . Note that is a partition of into countably many disjoint subsets. As , there exists an such that . Define . On this positive-measure subset, all witnessing gales run within a common polynomial time bound. Using Lemma 40, there exists an exact polynomial-time computable -gale that succeeds on all sequences in . Since is polynomial-time computable, it is automatically polynomial-time -approximable. Now, since we know that , we obtain a contradiction to Lemma 25. Hence, it must be the case that there exists a sequence with . Since was arbitrary, the theorem follows.
The same argument also gives an almost-sure version over the samplable source obtained from Lemma 25.
Lemma 42.
If one-way functions exist then for some , there exist a polynomial-time samplable distribution over such that:
-
1.
The number of random bits used by the sampler for on input is at most .
-
2.
For every and polynomial-time -approximable -supergale , .
-
3.
We now strengthen the conclusion by amplifying the gap. The above route naturally yields the threshold because the forward implication only rules out success of -approximable gales below . To push the separation to , we keep the same blueprint (construct a low- source and diagonalize against efficient betting strategies), but we modify the diagonalization so that it is carried out against exact computable gales. This avoids the accumulation of approximation slack, which becomes the bottleneck near dimension , and allows us to push the lower bound on to while keeping below .
Theorem 23. [Restated, see original statement.]
If one-way functions exist, then for any , there exists such that .
We prove the following stronger statement independently since it does not follow directly using the techniques in the proofs of Lemma 25 and Theorem 41. The main obstacle is that techniques involving approximable gales introduce non-negligible approximation errors while trying to achieve gaps close to . In the proof of the below theorem we instead employ computable gales. Whether Lemma 25 can be strengthened to yield such a gap remains an open question.
Theorem 43.
If one-way functions exist, then for every there exist set and a sequence such that and respectively.
The argument follows the same overall blueprint as the proof of Theorem 22: we use the PRG-induced mapping to produce sequences with low , and then diagonalize against efficient betting strategies by converting a successful -gale into a martingale that must exhibit large multiplicative gains at dyadic checkpoints, which yields a distinguisher for the underlying PRG. The only substantive change is that, to obtain gaps arbitrarily close to , we carry out the diagonalization using exact polynomial-time computable gales rather than -approximable gales, so that no approximation slack accumulates when we test many intermediate prefixes. A similar argument yields the corresponding separation statement for sets, by applying the same support/compactness reduction and the same diagonalization idea at the level of collections rather than individual sequences.
We obtain the following corollary of Theorem 43. This result provides a strong negative answer to the open question posed by Stull in [36] under the assumption that one-way functions exist.
Corollary 44.
If one-way functions exist then for every there exists such that .
5 Open Problems and Discussion
Our findings suggest several promising directions for future research. A key open question is whether weaker hardness assumptions, such as , or , can be characterized in terms of separations of polynomial-time dimension, as defined using time-bounded -gales and time-bounded Kolmogorov complexity in appropriate settings. Related work on time-bounded Kolmogorov complexity has also revealed connections with average-case hardness and one-way functions [25, 9]. Specifically, can these hardness assumptions be equivalently expressed through if-and-only-if statements involving polynomial-time dimension?
A different direction is to seek finite-length versions of these phenomena. Polynomial-time dimension is asymptotic, while the pseudorandomness assumptions used in this paper are finite-length indistinguishability assumptions. It would be interesting to define finite-length measures based on efficient online betting strategies, or equivalently log-loss prediction on -bit samples, and compare them with finite-time Kolmogorov complexity rates. Can one obtain finite-length separation theorems between efficient betting and efficient compression that characterize one-way functions, average-case hardness, or other standard assumptions?
Another natural direction concerns extraction and dimension amplification. Standard randomness extractors transform weak finite sources into distributions close to uniform [37], while dimension measures asymptotic randomness rates along individual infinite sequences. Can seeded extractors, condensers, or related pseudorandomness objects be lifted to transformations that increase polynomial-time dimension for typical outputs of efficiently samplable infinite sources? A complementary question is whether cryptographic hardness can be used to construct efficiently samplable sources whose finite prefixes have substantial entropy, but whose polynomial-time dimension cannot be increased by these transformations.
Our results reveal a duality between the non-robustness of polynomial-time dimension and the existence of one-way functions. An interesting open question is whether notions of polynomial-time randomness, defined via betting algorithms and Kolmogorov incompressibility of prefixes (see [36] for more details), capture equivalent concepts of randomness. Polynomial-time betting algorithms that succeed on specific sequences do not necessarily provide guarantees on the rate of capital accumulation in general. Consequently, investigating the robustness of polynomial-time randomness and its potential connections to cryptographic and complexity-theoretic primitives may require fundamentally new approaches.
References
- [1] Krishna B Athreya, John M Hitchcock, Jack H Lutz, and Elvira Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM journal on computing, 37(3):671–705, 2007. doi:10.1137/S0097539703446912.
- [2] Patrick Billingsley. Probability and measure. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, third edition, 1995. A Wiley-Interscience Publication.
- [3] Andrej Bogdanov and Luca Trevisan. Average-case complexity. Found. Trends Theor. Comput. Sci., 2(1):1–106, December 2006. doi:10.1561/0400000004.
- [4] Chris Bourke, John M. Hitchcock, and N. V. Vinodchandran. Entropy rates and finite-state dimension. Theoretical Computer Science, 349(3):392–406, 2005. doi:10.1016/J.TCS.2005.09.040.
- [5] Jack J. Dai, James I. Lathrop, Jack H. Lutz, and Elvira Mayordomo. Finite-state dimension. Theoretical Computer Science, 310(1-3):1–33, 2004. doi:10.1016/S0304-3975(03)00244-5.
- [6] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. doi:10.1109/TIT.1976.1055638.
- [7] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010. doi:10.1007/978-0-387-68441-3.
- [8] Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 416–426. ACM, 1990. doi:10.1145/100216.100272.
- [9] Halley Goldberg and Valentine Kabanets. Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), volume 317 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1–51:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.51.
- [10] Oded Goldreich. Foundations of Cryptography. Cambridge University Press, 2001.
- [11] Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. doi:10.1017/CBO9780511804106.
- [12] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984. doi:10.1016/0022-0000(84)90070-9.
- [13] Shuichi Hirahara and Mikito Nanashima. Learning in pessiland via inductive inference. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 447–457. IEEE, 2023. doi:10.1109/FOCS57990.2023.00033.
- [14] J.M. Hitchcock and N.V. Vinodchandran. Dimension, entropy rates, and compression. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 174–183, 2004. doi:10.1109/CCC.2004.1313835.
- [15] John M. Hitchcock. Effective fractal dimension: Foundations and applications. Ph.D. thesis, Iowa State University, 2003.
- [16] John M. Hitchcock and N.V. Vinodchandran. Dimension, entropy rates, and compression. Journal of Computer and System Sciences, 72(4):760–782, 2006. doi:10.1016/j.jcss.2005.10.002.
- [17] Johan HÅstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999. doi:10.1137/S0097539793244708.
- [18] Rahul Ilango, Hanlin Ren, and Rahul Santhanam. Robustness of average-case meta-complexity via pseudorandomness. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1575–1583, 2022. doi:10.1145/3519935.3520051.
- [19] R. Impagliazzo and L. A. Levin. No better ways to generate hard np instances than picking uniformly at random. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 812–821, 1990. doi:10.1109/FSCS.1990.89604.
- [20] R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In 30th Annual Symposium on Foundations of Computer Science, pages 230–235, 1989. doi:10.1109/SFCS.1989.63483.
- [21] Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, pages 73–79, New York, NY, USA, 2000. Association for Computing Machinery. doi:10.1145/335305.335314.
- [22] Andrei N Kolmogorov. Three approaches to the quantitative definition ofinformation’. Problems of information transmission, 1(1):1–7, 1965.
- [23] L. A. Levin. The tale of one-way functions. Probl. Inf. Transm., 39(1):92–103, January 2003. doi:10.1023/A:1023634616182.
- [24] Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008.
- [25] Yanyi Liu and Rafael Pass. On one-way functions and kolmogorov complexity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1243–1254, 2020. doi:10.1109/FOCS46700.2020.00118.
- [26] María López-Valdés and Elvira Mayordomo. Dimension is compression. In Joanna Jędrzejowicz and Andrzej Szepietowski, editors, Mathematical Foundations of Computer Science 2005, volume 3618 of Lecture Notes in Computer Science, pages 676–685, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11549345_58.
- [27] Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236–1259, 2003. doi:10.1137/S0097539701417723.
- [28] Jack H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49–79, 2003. doi:10.1016/S0890-5401(03)00187-1.
- [29] Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inform. Process. Lett., 84(1):1–3, 2002. doi:10.1016/S0020-0190(02)00343-5.
- [30] Moni Naor. Bit commitment using pseudorandomness. J. Cryptol., 4(2):151–158, January 1991. doi:10.1007/BF00196774.
- [31] Andre Nies. Computability and Randomness. Oxford University Press, Inc., USA, 2009.
- [32] K.W. Regan and D. Sivakumar. Probabilistic martingales and bptime classes. In Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247), pages 186–200, 1998. doi:10.1109/CCC.1998.694604.
- [33] John Rompel. One-way functions are necessary and sufficient for secure signatures. In Symposium on the Theory of Computing, 1990. URL: https://api.semanticscholar.org/CorpusID:10858937.
- [34] Halsey Lawrence Royden and Patrick Fitzpatrick. Real analysis, volume 32. Macmillan New York, 1988.
- [35] George F. Simmons. Introduction to Topology and Modern Analysis. McGraw-Hill, New York, 1963.
- [36] Donald M. Stull. Resource bounded randomness and its applications. In Johanna N. Y. Franklin and Christopher P. Porter, editors, Algorithmic Randomness: Progress and Prospects, Lecture Notes in Logic, pages 301–348. Cambridge University Press, Cambridge, 2020.
- [37] Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1–3):1–336, 2012. doi:10.1561/0400000010.
- [38] Andrew C. Yao. Protocols for secure computations. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 160–164, 1982. doi:10.1109/SFCS.1982.38.
