Alexey Milovanov
Computer Scientist
I am a researcher specializing in Computational Complexity, Algorithmic Information Theory, and Logic. I recently concluded my postdoctoral research at the Faculty of Science, University of Lisbon.
My recent work includes resolving open problems regarding the computational power of random strings (posed by E. Allender) and formalizing Kolmogorov complexity in Lean 4.
Recent Work
-
Limit on the computational power of C-random strings (2026). ECCC Report TR26-034. [ECCC]
💡 Solution to a problem posed by Eric Allender -
On the computational power of C-random strings. CiE 2025, Lisbon. [arXiv]
🏆 Best Paper Award 💡 Solution to a problem posed by Eric Allender - The hardness of decision tree complexity (with Bruno Loff). STACS 2025. [Dagstuhl]
-
Formalization of Algorithmic Information Theory in Lean 4.
[GitHub Repository]
▶ Show Full List of Publications
-
On the computational power of C-random strings. CiE 2025, Lisbon. [arXiv]
🏆 Best Paper Award 💡 Solution to a problem posed by Eric Allender - The hardness of decision tree complexity (with Bruno Loff). STACS 2025. [Dagstuhl]
- Predictions and Algorithmic Statistics for Infinite Sequences / Prediction and MDL for infinite sequences. CSR 2021 & Theory Computing Systems 2024. [arXiv]
- Some Games on Turing Machines and Power from Random Strings. CiE 2023. LNCS, vol 13967. Springer. [Springer]
- #P-completeness of counting roots of a sparse polynomial. Information Processing Letters. 2019. Vol. 142. [arXiv]
- Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms. CiE 2018. Springer, 2018. [Springer]
-
On Algorithmic Statistics for Space-Bounded Algorithms. CSR 2017 & Theory of Computing Systems 2019. [arXiv]
🏆 Best Student Paper Award - Stochasticity in Algorithmic Statistics for Polynomial Time (with Nikolay Vereshchagin). CCC 2017. [Dagstuhl]
-
Algorithmic Statistics: Normal Objects and Universal Models. CSR 2016, LNCS 9691. [arXiv]
💡 Solution to the problems posed by N. Vereshchagin - Algorithmic statistics, prediction and machine learning. STACS 2016, LIPICS Vol. 47. [Dagstuhl]
-
Some properties of antistochastic strings. CSR 2015 & Theory of Computing Systems 2017. [arXiv]
🏆 Best Student Paper Award