One-Way Functions and Polynomial Time Dimension
The 30th International Conference on Randomization and Computation, RANDOM 2026, Boston, USA.
To appear.
Subin Pulari
Assistant Professor
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 from 2024 to 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
Finite-State Dimension for Continued Fractions: Betting, Entropy and Normality
51st International Symposium on Mathematical Foundations of Computer Science, MFCS 2026, Paris, France.
To appear.
On Normality and Equidistribution for Separator Enumerators
Computability in Europe, CiE 2026, Trier, Germany.
To appear.
Randomness Extraction Fails for Finite-State Dimension
41st Annual Symposium on Logic in Computer Science, LICS 2026, Lisbon, Portugal.
To appear.
A Markov-Chain Characterization of Finite-State Dimension and a Generalization of Agafonov's Theorem
17th Latin American Theoretical Informatics Symposium, LATIN 2026, Florianópolis, Brazil.
To appear.
The Agafonov and Schnorr-Stimm Theorems for Probabilistic Automata
45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2025, Goa, India.
Point-to-Set Principle and Constructive Dimension Faithfulness
49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia.
A Weyl Criterion for Finite-State Dimension and Applications
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, Bordeaux, France.
Real Numbers Equally Compressible in Every Base
40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, Hamburg, Germany. Invited to the STACS special issue of ACM Transactions on Computation Theory.
Finite-State Relative Dimension and the Dimensions of A.P. Subsequences
17th Annual Conference on Theory and Applications of Models of Computation, TAMC 2022, Tianjin, China.
Ergodic Theorems for PSPACE Functions and Their Converses
46th International Symposium on the Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia.
Journal Publications
Real Numbers Equally Compressible in Every Base
ACM Transactions on Computation Theory, 2025.
Finite-State Relative Dimension, Dimensions of A.P. Subsequences and a Finite-State van Lambalgen's Theorem
Information and Computation, Volume 298, June 2024, 105156.
Ergodic Theorems and Converses for PSPACE Functions
Theory of Computing Systems, 2022.
An Analogue of Pillai's Theorem for Continued Fraction Normality and an Application to Subsequences
Bulletin of the London Mathematical Society, Volume 53, Issue 5, October 2021, pages 1414–1428.