Showing cs.CCShow all
2 papers · 1 filter
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.CC2020
Ergodic Theorems for PSPACE functions and their converses
Satyadev Nandakumar, Subin Pulari
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arb…