5 papers
On Effective Banach-Mazur Games and an application to the Poincaré Recurrence Theorem for Category
Prajval Koul, Satyadev Nandakumar
The classical Banach-Mazur game characterizes sets of first category in a topological space. In this work, we show that an effectivized version of the game yields a characterizatio…
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…
On the Constructive Dimension Spectrum of Polynomials
Prajval Koul, Satyadev Nandakumar
Recently, Stull [18], [17] resolved a long-standing open problem posed by Lutz, on whether the set of effective Hausdorff dimensions of points on a straight line in …
Point-to-set Principle and Constructive Dimension Faithfulness
Satyadev Nandakumar, Subin Pulari, Akhil S
Hausdorff -dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce an effective version of Hausdorff -dimension,…
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}_…