Subin Pulari

Assistant Professor
Big Data and Information Retrieval School · Faculty of Computer Science
HSE University Moscow
Email: · CV (PDF)

About

I am an Assistant Professor in the Big Data and Information Retrieval School, Faculty of Computer Science, HSE University Moscow, where I have been since 2025. Previously, I was a CNRS postdoctoral researcher at LaBRI, Université de Bordeaux (2024–2025), hosted by Laurent Bienvenu. I received my Ph.D. and M.Tech. in Computer Science and Engineering from IIT Kanpur in 2024, advised by Satyadev Nandakumar and Sunil Simon. I obtained my B.Tech. in Computer Science and Engineering from NIT Calicut in 2018.

My primary interests are algorithmic information theory, computational complexity, and computable analysis.

Conference Publications

  1. A Markov-Chain Characterization of Finite-State Dimension and a Generalization of Agafonov's Theorem (joint work with Laurent Bienvenu and Hugo Gimbert)
    • 17th Latin American Theoretical Informatics Symposium (LATIN 2026), Florianópolis, Brazil (To Appear)
    • ArXiv: [Link]
    • PDF: [Link]
  2. The Agafonov and Schnorr-Stimm theorems for probabilistic automata (joint work with Laurent Bienvenu and Hugo Gimbert)
    • 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025), Goa, India [Link]
    • ArXiv: [Link]
    • PDF: [Link]
  3. Point-to-set Principle and Constructive Dimension Faithfulness (joint work with Satyadev Nandakumar and Akhil S)
    • 49th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2024, Bratislava, Slovakia [Link]
    • ArXiv: [Link]
  4. A Weyl Criterion for Finite-State Dimension and Applications (joint work with Jack H. Lutz and Satyadev Nandakumar)
    • 48th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2023, Bordeaux, France [Link]
    • ArXiv: [Link]
  5. Real numbers equally compressible in every base (joint work with Satyadev Nandakumar)
    • 40th International Symposium on Theoretical Aspects of Computer Science (STACS) 2023, Hamburg, Germany, 2023 [Link]
    • Invited to the STACS special issue of ACM Transactions on Computation Theory.
    • ArXiv: [Link]
  6. Finite-State Relative Dimension and the Dimensions of AP Subsequences (joint work with Satyadev Nandakumar and Akhil S)
    • The 17th Annual Conference on Theory and Applications of Models of Computation (TAMC) 2022, Tianjin, China [Link]
    • ArXiv: [Link]
  7. Ergodic Theorems for PSPACE functions and their converses (joint work with Satyadev Nandakumar)
    • 46th International Symposium on the Mathematical Foundations of Computer Science (MFCS) 2021, Tallinn, Estonia [Link]
    • ArXiv: [Link]

Journal Publications

  1. Real numbers equally compressible in every base (joint work with Satyadev Nandakumar)
    • ACM Transactions on Computation Theory (2025) [Link]
  2. Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem (joint work with Satyadev Nandakumar and Akhil S)
    • Information and Computation , Volume 298, June 2024, 105156 [Link]
  3. Ergodic Theorems and Converses for PSPACE Functions (joint work with Satyadev Nandakumar)
    • Theory of Computing Systems (2022) [Link]
  4. An analogue of Pillai's theorem for continued fraction normality and an application to subsequences (joint work with Satyadev Nandakumar, Prateek Vishnoi and Gopal Viswanathan)
    • Bulletin of the London Mathematical Society, Volume 53, Issue 5, October 2021, Pages 1414-1428 [Link]
    • ArXiv: [Link]

Preprints

  1. One-Way Functions and Polynomial Time Dimension (joint work with Satyadev Nandakumar, Akhil S and Suronjona Sarma)
  2. On Normality and Equidistribution for Separator Enumerators
  3. Efficient Constructions of Finite-State Independent Normal Pairs