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}_…