3 papers
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.IT2025
Product gales and Finite state dimension
Akhil S
In this work, we introduce the notion of product gales, which is the modification of an -gale such that separate bets can be placed at each symbol. The product of the bets p…
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}_…