11 papers
Efficient Constructions of Finite-State Independent Normal Pairs
Subin Pulari
Finite-state independence is a robust notion of algorithmic independence for infinite words. It was introduced for general infinite words by Becher, Carton, and Heiber via determin…
On Normality and Equidistribution for Separator Enumerators
Subin Pulari
A separator is a countable dense subset of , and a separator enumerator is a naming scheme that assigns a real number in to each finite word so that the set of all n…
A Markov-Chain Characterization of Finite-State Dimension and a Generalization of Agafonov's Theorem
Laurent Bienvenu, Hugo Gimbert, Subin Pulari
Finite-state dimension quantifies the asymptotic rate of information in an infinite sequence as perceived by finite automata. For a fixed alphabet, the infinite sequences that have…
The Agafonov and Schnorr-Stimm theorems for probabilistic automata
Laurent Bienvenu, Hugo Gimbert, Subin Pulari
For a fixed alphabet , an infinite sequence is said to be normal if every word over appears in with the same frequency as any other word of the same length. A cl…
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}_…
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, w…
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…
Real numbers equally compressible in every base
Satyadev Nandakumar, Subin Pulari
This work solves an open question in finite-state compressibility posed by Lutz and Mayordomo about compressibility of real numbers in different bases. Finite-state compressibility…
A Weyl Criterion for Finite-State Dimension and Applications
Jack H. Lutz, Satyadev Nandakumar, Subin Pulari
Finite-state dimension, introduced early in this century as a finite-state version of classical Hausdorff dimension, is a quantitative measure of the lower asymptotic density of in…
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…
An analogue of Pillai's theorem for continued fraction normality and an application to subsequences
Satyadev Nandakumar, Subin Pulari, Prateek Vishnoi +1
We show that two notions of continued fraction normality, one where overlapping occurrences of finite patterns are counted as distinct occurrences, and another where only disjoint…