2 citations · 2 across the 15 of their papers we have counts for
6 papers · 1 filter
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…
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}_…
Ergodic Theorems for PSPACE functions and their converses
Satyadev Nandakumar, Subin Pulari
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arb…
On Resource-bounded versions of the van Lambalgen theorem
Diptarka Chakraborty, Satyadev Nandakumar, Himanshu Shukla
The van Lambalgen theorem is a surprising result in algorithmic information theory concerning the symmetry of relative randomness. It establishes that for any pair of infinite sequ…
Axiomatizing Resource Bounds for Measure
Xiaoyang Gu, Jack H. Lutz, Satyadev Nandakumar +1
Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the {\it…
Finite-State Dimension and Real Arithmetic
David Doty, Jack H. Lutz, Satyadev Nandakumar
We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+al…