Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > AKHIL S:
All reports by Author Akhil S:

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

One-Way Functions and Polynomial Time Dimension

Revisions: 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}_\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