4 papers
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 st…
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…
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}_…
Finite-State Relative Dimension, dimensions of A. P. subsequences and a Finite-State van Lambalgen's theorem
Satyadev Nandakumar, Subin Pulari, Akhil S
Finite-state dimension (Dai, Lathrop, Lutz, and Mayordomo (2004)) quantifies the information rate in an infinite sequence as measured by finite-state automata. In this paper, we de…