Papers in reverse chronological order.

  1. Point-to-set Principle and Constructive Dimension Faithfulness (joint work with Subin Pulari and Akhil S.), 49th Conference on the Mathematical Foundations of Computer Science (MFCS 2024), Bratislava, Slovakia. [PDF]

    Summary. Generalizes classical and effective Hausdorff dimension to a larger family of coverings, which includes base-b expansions of reals, Cantor series expansions of reals and continued fractions. A cover family is said to be faithful if, for every set, the dimension we compute using these covers is the same as Hausdorff dimension. We investigate whether classical dimension is preserved precisely when effective pointwise dimension is preserved, by proving a "point-to-set principle" for faithfulness.

  2. Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem. Information and Computation (accepted for publication, 2024).

    Summary. Introduces a robust, relativized notion of finite-state dimension. Using this, we show that van Lambalgen's theorem works for finite-state randoms (i.e. normal numbers). This is the first "resource-bounded" setting where van Lambalgen's theorem is known to hold. We also get a stronger version of Wall's theorem on A. P. subsequences of normals, which characterizes normals, unlike Wall's original theorem.

  3. A Weyl Criterion for Finite-State Dimension (joint work with Jack Lutz and Subin Pulari), 48th Conference on Mathematical Foundations of Computer Science, Bordeaux, France, 2023. (MFCS 2023) [PDF]

    Summary. Generalizes Weyl critierion for normality (1916), which works for almost all reals (those which are normal), to work for all reals, without exception. (This turns out to be highly non-trivial.) We show, using the theory of weak convergence of probability measures and Rényi dimension of weak limits, how Weyl exponential averages, even divergent ones, relate to finite-state dimension (finite-state compressibility).

  4. Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals (joint work with Akhil S. and Prateek Vishnoi), 48th Conference on Mathematical Foundations of Computer Science, Bordeaux, France, 2023. (MFCS 2023) [PDF]

    Summary. Shows that effective Hausdorff dimension of base-b expansions and effective continued fraction dimensions are not the same for every real, contrary to expectations.

  5. Real numbers equally compressible in every base (joint work with Subin Pulari), [PDF], 40th Symposium on Theoretical Aspects of Computer Science, Hamburg, 2023. (STACS 2023) (invited to the special issue)

    Summary. Answers an open question posed by Lutz (2012), and Lutz, Mayordomo (2020). Just as there are absolutely normal numbers, and numbers which have 0 finite-state dimension in every base, they asked, are there numbers which have the same intermediate finite-state dimension, say s, 0 < s < 1, in every base b > 2? We provide an explicit construction for such a number, showing more generally that any reasonable set of dimension requirements for different bases can be met by a single real.

    (This paper got a mention in Richard Lipton's blog.)

  6. Ergodic theorems and converses for PSPACE functions (joint work with Subin Pulari). Theory of Computing Systems 67 pp 491-520, 2023. (commemorative volume for Alan Selman) [ LINK]
  7. Finite-State Relative Dimension and the Dimensions of AP Subsequences (joint work with Subin Pulari and Akhil S), 17th Annual Conference on Theory and Applications of Models of Computation 2022, (TAMC 2022) Tianjin, China, 2022. [PDF]
  8. Ergodic theorems and converses for PSPACE functions (joint work with Subin Pulari), 46th International Symposium on the Mathematical Foundations of Computer Science 2021 (MFCS 2021), Tallin, Estonia. [ArXiv]

    Summary. Studies ergodic theorems in resource-bounded settings for the first time. We focus on ergodic averages of PSPACE functions on PSPACE and SUBEXP space randoms, establishing sufficient conditions in the first, and characterizations in the second, for ergodicity on these randoms.

  9. On continued fractions and normality (joint work with Prateek Vishnoi). Information and Computation. Volume 285, Part B, 2022, 104876.[ LINK]
  10. An analogue of Pillai's theorem for continued fraction normality and and application to subsequences (joint work with Subin Pulari, Prateek Vishnoi and Gopal Viswanathan). Bulletin of the London Mathematical Society, 53(5):1414-1428, 2021. [PDF]

    Summary. S. S. Pillai showed that base-b normality can be equivalently defined by considering "overlapping" occurrences of blocks, as well as disjoint occurrences of blocks, and these two notions are the same for all base-b normals. We show the analogous equivalence for continued fraction normality. We demonstrate its utility by giving a combinatorial proof of Heersink and Vandehey's surprising result that A.P. subsequences of continued fraction normals are never normal.

  11. Randomness and effective dimension of continued fractions (joint work with Prateek Vishnoi), 45th International Symposium on the Mathematical Foundations of Computer Science 2020 (MFCS 2020), Prague, Czech Republic.[PDF]

    Summary. We define the notion of computably random continued fraction (c.e. randomness was previously known). We show that these are precisely the computable randoms. Further, we define effective Hausdorff dimensions of individual continued fractions and provide explicit constructions of continued fractions with dimensions 0 and 1.

  12. A weak-2 generic which bounds a minimal degree, (joint work with Rod Downey). Journal of Symbolic Logic 84(4): 1326-1347, 2019. [PDF]

    Summary. We answer an open question by Barmpalias and Lewis-Pye (2014), and show that there is a weak-2 generic that bounds a minimal degree. This implies that weak-2 generics are not dense. Earlier, Jockusch had shown that 2 generics are dense, and Kumabe, Chong and Downey had shown that 1 generics are not dense.

  13. Martin-Löf randomness implies multiple recurrence in effectively closed sets, (joint work with Rod Downey and André Nies), Notre Dame of Formal Logic, 60(3):491-502, 2019.[PDF]

    Summary. This paper shows that the Furstenberg multiple recurrence theorem holds effectively - that is, for systems that are suitably computable, and which satisfy the Furstenberg conditions, every Martin-Löf random is multiply recurrent in effectively closed sets.

  14. Dimension, Pseudorandomness and Extraction of Pseudorandomness (joint work with Manindra Agrawal, Diptarka Chakraborty and Debarati Das), Computability vol. 6, no. 3, pp. 277-305, 2017. [PDF]

    Summary. This paper adapts the theory of effective dimension by Lutz and others, to quantify the amount of randomness present in pseudorandom distributions.

  15. On Resource-Bounded van Lambalgen's Theorems (joint work with Diptarka Chakraborty and Himanshu Shukla), 14th Annual Conference on Theory and Applications of Models of Computation, (TAMC 2017) Bern 2017. [PDF]

    Summary. We show that resource-bounded versions of the van Lambalgen's theorem may not hold, and the mode of failure depends on the notion of resource-bounded randomness we use (i.e. compressibility versus betting). This paper also contains two new proofs of the classical van Lambalgen's theorem.

  16. Dimension, Pseudorandomness and Extraction of Pseudorandomness (joint work with Manindra Agrawal, Diptarka Chakraborty and Debarati Das), 35th Foundations of Software Technology and Theoretical Computer Science, (FSTTCS 2015) Bangalore 2015. [PDF]
  17. Normality and Finite-State Dimension of Liouville Numbers (joint work with Santosh Kumar Vangepalli.) Special Issue for CCR 2013, Theory of Computing Systems, 8 June 2014 (online), pages 1-11.

    Summary. Gives a nearly linear-time construction of a certain class of transcendental numbers, namely Liouville numbers, which are normal - i.e. look random to finite-state compressors. The result is surprising since the standard examples of Liouville numbers all are highly compressible, so it was conceivable that all of them are compressible. The construction contains two key insights - one, that the "padding" inside a Liouville number need not be zeroes, it can be any pattern, even a random-looking one, and two, by using rationals with repeating non-zero blocks as approximations (instead of rationals truncated with zeroes), we can control the diophantine approximation.

    We also give Liouville numbers for intermediate compressibilities between 0 and 1.

  18. Multiple Recurrence and Algorithmic Randomness (joint work with Rodney G. Downey and André Nies), 10th International Conference on Computability and Randomness, (CCR 2015) Heidelberg, Germany, 2015. [PDF]
  19. Ornstein Isomorphism and Algorithmic Randomness (joint work with Mrinalkanti Ghosh and Atanu Pal), 9th International Conference on Computability and Randomness, (CCR 2014) Singapore, 2014. [PDF]

    (see: reading list on algorithmic information theory, by C. Shalizi.)

  20. Normality and Finite-State Dimension of Liouville Numbers (joint work with Santosh Kumar Vangepalli.) (CCR 2013) 8thInternational Conference on Computability and Randomness, Moscow, Russia, 2013. (invited to the Special Issue) [PDF]
  21. Predictive Complexity and Generalized Entropy of Stationary Ergodic Processes, (joint work with Mrinalkanti Ghosh), 23rd Conference on Algorithmic Learning Theory, (ALT 2012) Lyon, France, 2012.[PDF]
  22. Axiomatizing Resource Bounded Measure (joint work with Xiaoyang Gu, Jack Lutz and Jim Royer),7th conference on Computability in Europe, (CiE 2011) Sofia, Bulgaria, 2011. [PDF]
  23. A Characterization of Constructive Dimension, Mathematical Logic Quarterly, 55 (3), 271-286, 2009.[PDF]
  24. An Effective Ergodic Theorem and Some Applications, 40th ACM Annual Symposium on Theory of Computing, (STOC 2008) Victoria, BC, Canada, 2008.[PDF]
  25. Finite State Dimension and Real Arithmetic(joint work with Dave Doty and Jack Lutz), Information and Computation, 205 (207), pp. 1640-1651, 2007.
  26. A Characterization of Constructive Dimension, Computability and Complexity in Analysis, (CCA 2007) Siena, Tuscany, Italy, 2007. [Slides] (This paper unfortunately contains an error, which was corrected in the journal version.)
  27. Finite State Dimension and Real Arithmetic, (joint work with David Doty and Jack Lutz) 33rd International Colloquium on Automata, Logic and Programming, (ICALP 2006) Venice, Italy, 2006.[PDF] [PS]

Workshop

  1. Axiomatizing Resource Bounded Measure (joint work with Xiaoyang Gu, Jack Lutz and Jim Royer), Logic and Computational Complexity, 2009. arXiv:1102.2095v1[PDF]

Preprints

  1. Martingales and Restricted Ratio Betting (joint work with Keng Meng Ng and S. Masulkar), [PDF]

Ph D. Thesis

Dynamics, Measure and Dimension in the Theory of Computing, Iowa State University, 2009.[PDF]

Co-authors (alphebetical order)

Manindra Agrawal   Diptarka Chakraborty   Rod Downey   Debarati Das   Dave Doty   Mrinalkanti Ghosh   Xiaoyang Gu   Jack Lutz   Sumedh Masulkar   Keng Meng (Selwyn) Ng   André Nies   Atanu Pal   Subin Pulari    Jim Royer   Akhil S.   Himanshu Shukla   Santhosh Kumar Vangapelli   Prateek Vishnoi   Gopal Viswanathan