3 papers
cs.CC2024
One-Way Functions and Polynomial Time Dimension
Satyadev Nandakumar, Subin Pulari, Akhil S +1
This paper demonstrates a duality between the non-robustness of polynomial time dimension and the existence of one-way functions. Polynomial-time dimension (denoted $\mathrm{cdim}_…
cs.IT2023
Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
Satyadev Nandakumar, Akhil S, Prateek Vishnoi
We establish that constructive continued fraction dimension originally defined using -gales is robust, but surprisingly, that the effective continued fraction dimension and effe…
cs.IT2023
Finite-State Relative Dimension, dimensions of A. P. subsequences and a Finite-State van Lambalgen's theorem
Satyadev Nandakumar, Subin Pulari, Akhil S
Finite-state dimension (Dai, Lathrop, Lutz, and Mayordomo (2004)) quantifies the information rate in an infinite sequence as measured by finite-state automata. In this paper, we de…