Nandakumar, Pulari, Akhil S, and Sarma (arXiv:2411.02392 / ECCC TR25-028) proved a duality between the non-robustness of polynomial-time dimension and cryptography: if one-way functions exist, then there is a short-seed polynomial-time samplable distribution over infinite binary sequences with respect to which the betting-based polynomial-time dimension and the polynomial-time Kolmogorov complexity rate are separated by a uniform gap with probability one; conversely, the existence of such a dimension-gap distribution is known to imply the existence of infinitely-often one-way functions. The exact strength of the dimension-gap phenomenon is open: it is not known whether the converse can be strengthened from infinitely-often to standard one-way functions, nor whether infinitely-often one-way functions already suffice for the forward direction. The problem asks to determine, by proof or by relativized separation, whether the existence of such distributions is equivalent to one-way functions, to infinitely-often one-way functions, or lies strictly between.

Background

A one-way function (OWF) is a polynomial-time computable function ff on finite strings that is hard to invert on average for every probabilistic polynomial-time algorithm; an infinitely-often OWF is the weaker primitive where hardness of inversion is required only at infinitely many input lengths rather than at all sufficiently large lengths. Whether the latter genuinely differs from the former is itself a long-standing open issue.

Resource-bounded dimension quantifies the density of information of an infinite binary sequence XX using betting strategies. An ss-gale (for 0≤s≤10 \le s \le 1) is a generalization of a martingale, i.e., of a capital process for a gambler betting on the successive bits of XX at fair odds, designed so that unbounded capital growth along XX testifies that XX carries at most ss bits of effective information per position; formally dd succeeds on XX when lim sup⁡nd(X↾n)=∞\limsup_n d(X \upharpoonright n) = \infty. The constructive dimension of XX, cdim⁡(X)\operatorname{cdim}(X), is the infimum of ss such that some computable ss-gale succeeds on XX, and its polynomial-time analogue cdim⁡P(X)\operatorname{cdim}_P(X) restricts to polynomial-time computable gales. A dual quantity, polynomial-time strong dimension, replaces the limsup implicit in the dimension by a liminf.

An alternative way to measure the polynomial-time information density of XX uses time-bounded Kolmogorov complexity: Kt(x)K^t(x) is the length of the shortest program printing xx within time t(∣x∣)t(|x|), and Kpoly(X)K_{\mathrm{poly}}(X) is the infimum over polynomials tt of lim inf⁡nKt(X↾n)/n\liminf_n K^t(X \upharpoonright n)/n. In the polynomial-space setting the two approaches coincide: Hitchcock and Vinodchandran (CCC 2004; JCSS 2006) proved cdim⁡PSPACE=KPSPACE\operatorname{cdim}_{\mathrm{PSPACE}} = K_{\mathrm{PSPACE}}, establishing robustness of polynomial-space dimension. In polynomial time they proved only the inequality Kpoly(X)≤cdim⁡P(X)K_{\mathrm{poly}}(X) \le \operatorname{cdim}_P(X) for every XX, and asked — a question later restated in Stull's 2020 survey — whether equality always holds.

Nandakumar, Pulari, Akhil S, and Sarma answered this negatively under the OWF assumption. Their main theorem (Theorem 5) shows that if OWFs exist, then for every s<1/2s < 1/2 there is a distribution ν\nu over infinite sequences that is polynomial-time samplable in a short-seed sense — the sampler uses at most snsn random bits to produce a string of length nn — such that every polynomial-time s′s'-supergale with s<s′<1/2s < s' < 1/2 that is ν\nu-approximable succeeds on a set of ν\nu-measure zero. Here an s′s'-supergale relaxes the fair-betting equality d(w)=(d(w0)+d(w1))/2s′d(w) = (d(w0) + d(w1))/2^{s'} required of an s′s'-gale to the inequality d(w)≥(d(w0)+d(w1))/2s′d(w) \ge (d(w0) + d(w1))/2^{s'} (a supermartingale-type condition with growth factor 2s′2^{s'}), and ν\nu-approximability means the gale's values can be approximated within a constant factor by a probabilistic polynomial-time machine outside a set of small ν\nu-measure at each length; this bridges the deterministic nature of gales with probabilistic samplers. Short seeds force Kpoly(X)≤sK_{\mathrm{poly}}(X) \le s with probability one over ν\nu, while the supergale condition forces cdim⁡P(X)≥1/2\operatorname{cdim}_P(X) \ge 1/2 almost surely, so the two dimension notions are separated by a uniform gap on a measure-one set. The authors furthermore derive sequences XX with cdim⁡P(X)−Kpoly(X)≥1−ϵ\operatorname{cdim}_P(X) - K_{\mathrm{poly}}(X) \ge 1 - \epsilon for any ϵ>0\epsilon > 0.

In the converse direction (Lemma 2), the existence of such a dimension-gap distribution implies the existence of infinitely-often OWFs. The proof goes through the universal extrapolation theorem of Ilango, Ren, and Santhanam (STOC 2022), which states, roughly, that if no infinitely-often OWFs exist then every polynomial-time samplable distribution can be extrapolated, i.e., its next bits predicted from its prefixes with inverse-polynomial error, by a polynomial-time algorithm.

The duality is therefore strictly incomplete, and the authors identify the obstacles precisely. For the forward direction, deriving the gap distribution from infinitely-often OWFs would require breaking the underlying constant-stretch pseudorandom generators (PRGs, efficiently computable algorithms that stretch short random seeds into longer strings that no polynomial-time distinguisher can tell apart from uniform randomness) at all but finitely many lengths, but a winning s′s'-gale accumulates unbounded capital only infinitely often, with no guarantee of any eventual rate of capital doubling, so the needed doubling conditions may fail at infinitely many lengths. For the converse, absent full OWFs the extrapolation-based approximation of the sampler succeeds only at infinitely many rather than at every input length, so the constructed supergale is ν\nu-approximable only in this weaker sense; the authors prove (their Lemma 15) that if the distribution defeats even the larger class of supergales that are ν\nu-approximable merely on infinitely many lengths, then standard OWFs do follow, which pinpoints the exact slack in the current state of knowledge.

Problem Statement

Determine the exact cryptographic strength of the dimension-gap phenomenon of Nandakumar, Pulari, Akhil S, and Sarma. Let a dimension-gap distribution be a probability distribution ν\nu over infinite binary sequences such that: (1) ν\nu is polynomial-time samplable and the sampler uses at most snsn random bits to sample a string of length nn, for some constant s<1s < 1 (a short seed); and (2) for every s′s' in an open interval above ss and every polynomial-time s′s'-supergale dd that is ν\nu-approximable (approximable within a constant factor by a probabilistic polynomial-time machine outside a set of inverse-polynomially small ν\nu-measure at each length), the success set of dd has ν\nu-measure zero. The paper proves that OWFs imply the existence of such distributions (for every s<1/2s < 1/2), and that the existence of such distributions implies infinitely-often OWFs. Two directions remain open:

(i) Does the existence of a dimension-gap distribution imply the existence of standard one-way functions, or only infinitely-often one-way functions? Equivalently, can the approximability slack identified in Lemma 15 of the source — supergales that are ν\nu-approximable at every input length, as in the definition above, versus the larger class of supergales that are ν\nu-approximable merely on infinitely many input lengths — be closed?

(ii) Does the existence of infinitely-often one-way functions imply the existence of dimension-gap distributions, i.e., can the forward direction be proved from the weaker hypothesis?

Resolving both directions locates the existence of dimension-gap distributions exactly: equivalent to standard OWFs, equivalent to infinitely-often OWFs, or strictly between the two.

References

  1. Satyadev Nandakumar, Subin Pulari, Akhil S, and Suronjona Sarma. "One-Way Functions and Polynomial Time Dimension." arXiv:2411.02392 (2024), https://arxiv.org/abs/2411.02392; also ECCC Technical Report TR25-028 (2025), https://eccc.weizmann.ac.il/report/2025/028/.
  2. 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, https://doi.org/10.1016/j.jcss.2005.10.002.
  3. J. M. Hitchcock and N. V. Vinodchandran. "Dimension, entropy rates, and compression." Proceedings 19th IEEE Annual Conference on Computational Complexity (CCC 2004), pp. 174-183. DOI 10.1109/CCC.2004.1313835, https://doi.org/10.1109/CCC.2004.1313835.
  4. Donald M. Stull. "Resource bounded randomness and its applications." In Algorithmic Randomness (Lecture Notes in Logic), pp. 301-348. Cambridge University Press, 2020. DOI 10.1017/9781108781718.010, https://doi.org/10.1017/9781108781718.010.
  5. Rahul Ilango, Hanlin Ren, and Rahul Santhanam. "Robustness of average-case meta-complexity via pseudorandomness." Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), pp. 1575-1583. DOI 10.1145/3519935.3520051, https://doi.org/10.1145/3519935.3520051.
  6. Yanyi Liu and Rafael Pass. "On One-way Functions and Kolmogorov Complexity." 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 1243-1254. DOI 10.1109/FOCS46700.2020.00118, https://doi.org/10.1109/FOCS46700.2020.00118.
  7. Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira. "A Duality between One-Way Functions and Average-Case Symmetry of Information." Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pp. 1039-1050. DOI 10.1145/3564246.3585138, https://doi.org/10.1145/3564246.3585138.
  8. Marius Zimand. "On one-way functions and the average time complexity of almost-optimal compression." arXiv:2412.03392 (2024), https://arxiv.org/abs/2412.03392.
  9. John M. Hitchcock, Adewale Sekoni, and Hadi Shafei. "Counting Martingales for Measure and Dimension in Complexity Classes." 40th Computational Complexity Conference (CCC 2025), LIPIcs vol. 339, pp. 20:1-20:35. DOI 10.4230/LIPIcs.CCC.2025.20, https://doi.org/10.4230/LIPIcs.CCC.2025.20; arXiv:2508.07619, https://arxiv.org/abs/2508.07619.
  10. Satyadev Nandakumar, Akhil S, and Chandra Shekhar Tiwari. "Resource bounded Kučera-Gács Theorems." arXiv:2605.21546 (2026), https://arxiv.org/abs/2605.21546.