Search Results

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 dim_P, quantifies information density using polynomial-time betting strategies called s-gales. Polynomial-time Kolmogorov complexity rate, denoted 𝒦_poly, gives a compression-based notion of polynomial-time information density using polynomial-time descriptions. Hitchcock and Vinodchandran (CCC 2004) showed that dim_P(X) ≥ 𝒦_poly(X) for every sequence X, 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 1, the sampled sequence X satisfies dim_P(X) > 𝒦_poly(X) 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 dim_P and 𝒦_poly, and that the gap can be made arbitrarily close to 1. 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.