Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Resource bounded KuÄera-Gács Theorems
Satyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari
The KuÄera--Gács theorem is a fundamental result in algorithmic randomness. It states that every infinite sequence is Turing reducible to a Martin-Löf random . This paper…
cs.CC2025
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}_…