Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SURONJONA SARMA:
All reports by Author Suronjona Sarma:

TR25-028 | 12th March 2025
Satyadev Nandakumar, Subin Pulari, Akhil S, Suronjona Sarma

One-Way Functions and Polynomial Time Dimension

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}_\mathrm{P}$) quantifies the density of information of infinite sequences using polynomial time betting algorithms called $s$-gales. An alternate quantification of the notion of polynomial time density of information is ... more >>>




ISSN 1433-8092 | Imprint