Alexander Shen

ORCID

Publication Activity (10 Years)

Years Active: 1991-2024
Publications (10 Years): 46

Top Venues

Publications

Alexander Shen
Kolmogorov complexity as a combinatorial tool. CoRR (2024)
Alexander Shen
Kolmogorov Complexity as a Combinatorial Tool. CiE (2024)
Alexander Shen
Conditional normality and finite-state dimensions revisited. CoRR (2024)
Alexander Shen
The Kraft-Barmpalias-Lewis-Pye lemma revisited. CoRR (2023)
Ruslan Ishkuvatov, Daniil Musatov, Alexander Shen
Approximating Kolmogorov complexity. Comput. 12 (3) (2023)
George Barmpalias, Alexander Shen
The Kučera-Gács theorem revisited by Levin. Theor. Comput. Sci. 947 (2023)
Alexander Shen
Inequalities for Entropies and Dimensions. CiE (2023)
Ilir Çapuni, Jarkko Kari, Alexander Shen
Taming randomness and complexity - Essays in honour of Professor Péter Gács. Theor. Comput. Sci. 949 (2023)
Bruno Bauwens, Péter Gács, Andrei E. Romashchenko, Alexander Shen
Inequalities for space-bounded Kolmogorov complexity. Comput. 11 (3-4) (2022)
Alexander Shen
Inequalities for entropies and dimensions. CoRR (2022)
Andrei E. Romashchenko, Alexander Shen, Marius Zimand
27 Open Problems in Kolmogorov Complexity. CoRR (2022)
Alexander Shen
Individual codewords. Theor. Comput. Sci. 908 (2022)
Alexander Shen
Gács-Kučera's Theorem Revisited by Levin. CoRR (2021)
Alexander Shen
Individual codewords. CoRR (2021)
Andrei E. Romashchenko, Alexander Shen, Marius Zimand
27 Open Problems in Kolmogorov Complexity. SIGACT News 52 (4) (2021)
Alexander Kozachinskiy, Alexander Shen
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. J. Comput. Syst. Sci. 118 (2021)
Alexander Shen
Randomness Tests: Theory and Practice. Fields of Logic and Computation III (2020)
Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
On the Structure of Ammann A2 Tilings. Discret. Comput. Geom. 63 (3) (2020)
Alexander Shen
Complexity of majorants. CoRR (2020)
Péter Gács, Andrei E. Romashchenko, Alexander Shen
Inequalities for space-bounded Kolmogorov complexity. CoRR (2020)
Gleb Posobin, Alexander Shen
Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. STACS (2019)
Alexander Kozachinskiy, Alexander Shen
Two Characterizations of Finite-State Dimension. FCT (2019)
Alexander Shen
Axiomatic approach to the theory of algorithms and relativized computability. CoRR (2018)
Mikhail Andreev, Gleb Posobin, Alexander Shen
Plain Stopping Time and Conditional Complexities Revisited. MFCS (2018)
Laurent Bienvenu, Santiago Figueira, Benoit Monin, Alexander Shen
Algorithmic identification of probabilities is hard. J. Comput. Syst. Sci. 95 (2018)
Vladimir Uspenskiy, Alexander Shen
Algorithms and Geometric Constructions. CiE (2018)
Bruno Bauwens, Alexander Shen
Information Distance Revisited. CoRR (2018)
Gleb Posobin, Alexander Shen
Random noise increases Kolmogorov complexity and Hausdorff dimension. CoRR (2018)
Noam Greenberg, Joseph S. Miller, Alexander Shen, Linda Brown Westrick
Dimension 1 sequences are close to randoms. Theor. Comput. Sci. 705 (2018)
Alexander Shen
Automatic Kolmogorov complexity and normality revisited. CoRR (2017)
Nikolay K. Vereshchagin, Alexander Shen
Algorithmic Statistics: Forty Years Later. Computability and Complexity (2017)
Bruno Bauwens, Alexander Shen, Hayato Takahashi
Conditional Probabilities and van Lambalgen's Theorem Revisited. Theory Comput. Syst. 61 (4) (2017)
Alexander Shen
Automatic Kolmogorov Complexity and Normality Revisited. FCT (2017)
Alexander Shen
Compressibility and Probabilistic Proofs. CiE (2017)
Noam Greenberg, Joseph S. Miller, Alexander Shen, Linda Brown Westrick
Dimension 1 sequences are close to randoms. CoRR (2017)
Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
Layerwise Computability and Image Randomness. Theory Comput. Syst. 61 (4) (2017)
Mikhail Andreev, Gleb Posobin, Alexander Shen
Plain stopping time and conditional complexities revisited. CoRR (2017)
Alexander Shen
Compressibility and probabilistic proofs. CoRR (2017)
Nikolai K. Vereshchagin, Alexander Shen
Algorithmic statistics: forty years later. CoRR (2016)
Laurent Bienvenu, Damien Desfontaines, Alexander Shen
Generic algorithms for halting problem and optimal machines revisited. Log. Methods Comput. Sci. 12 (2) (2016)
Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
Layerwise computability and image randomness. CoRR (2016)
Laurent Bienvenu, Alexander Shen
-low Sequences: A Tutorial. Fields of Logic and Computation II (2015)
Nikolai K. Vereshchagin, Alexander Shen
Algorithmic statistics revisited. CoRR (2015)
Andrei E. Romashchenko, Alexander Shen
Topological Arguments for Kolmogorov Complexity. Theory Comput. Syst. 56 (3) (2015)
Laurent Bienvenu, Damien Desfontaines, Alexander Shen
What Percentage of Programs Halt? ICALP (1) (2015)
Alexander Shen
Around Kolmogorov complexity: basic notions and results. CoRR (2015)
Laurent Bienvenu, Benoit Monin, Alexander Shen
Algorithmic Identification of Probabilities Is Hard. ALT (2014)
Andrei Yu. Rumyantsev, Alexander Shen
Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma. Fundam. Informaticae 132 (1) (2014)
Laurent Bienvenu, Alexander Shen
K-trivial, K-low and MLR-low sequences: a tutorial. CoRR (2014)
Laurent Bienvenu, Andrei E. Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren
The axiomatic power of Kolmogorov complexity. Ann. Pure Appl. Log. 165 (9) (2014)
Bruno Bauwens, Alexander Shen
Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity. J. Symb. Log. 79 (2) (2014)
Bruno Bauwens, Alexander Shen
An Additivity Theorem for Plain Kolmogorov Complexity. Theory Comput. Syst. 52 (2) (2013)
Laurent Bienvenu, Andrei E. Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren
The axiomatic power of Kolmogorov complexity CoRR (2013)
Andrei Yu. Rumyantsev, Alexander Shen
Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma CoRR (2013)
Alexander Shen, Andrei E. Romashchenko
Topological arguments for Kolmogorov complexity AUTOMATA & JAC (2012)
Laurent Bienvenu, Alexander Shen
Random Semicomputable Reals Revisited. Computation, Physics and Beyond (2012)
Alexander Shen
Game arguments in computability theory and algorithmic information theory CoRR (2012)
Alexander Shen
Game Arguments in Computability Theory and Algorithmic Information Theory. CiE (2012)
Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, Alexander Shen
A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points. Inf. Comput. 210 (2012)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Fixed-point tile sets and their applications. J. Comput. Syst. Sci. 78 (3) (2012)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
Limit complexities revisited [once more] CoRR (2012)
Alexander Shen
Are random axioms useful? CoRR (2011)
Bruno Bauwens, Alexander Shen
An additivity theorem for plain complexity CoRR (2011)
Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen
Not every domain of a plain decompressor contains the domain of a prefix-free one. Theor. Comput. Sci. 412 (4-5) (2011)
Alexander Shen
Kolmogorov Complexity as a Language. CSR (2011)
Laurent Bienvenu, Péter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen
Algorithmic tests and randomness with respect to a class of measures CoRR (2011)
Alexander Shen
Kolmogorov complexity as a language CoRR (2011)
Daniil Musatov, Andrei E. Romashchenko, Alexander Shen
Variations on Muchnik's Conditional Complexity Theorem. Theory Comput. Syst. 49 (2) (2011)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
Limit Complexities Revisited. Theory Comput. Syst. 47 (3) (2010)
Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, Alexander Shen
A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points CoRR (2010)
Yen-Wu Ti, Ching-Lueh Chang, Yuh-Dauh Lyuu, Alexander Shen
Sets of k-Independent Strings. Int. J. Found. Comput. Sci. 21 (3) (2010)
Bruno Durand, Alexander Shen, Andrei E. Romashchenko
1D Effectively Closed Subshifts and 2D Tilings CoRR (2010)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Fixed point theorem and aperiodic tilings CoRR (2010)
Alexander Shen
Decomposition Complexity CoRR (2010)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Effective Closed Subshifts in 1D Can Be Implemented in 2D. Fields of Logic and Computation (2010)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
1D Effectively Closed Subshifts and 2D Tilings. JAC (2010)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Effective closed subshifts in 1D can be implemented in 2D CoRR (2010)
Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen
Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One CoRR (2010)
Vladimir Vovk, Alexander Shen
Prequential randomness and probability. Theor. Comput. Sci. 411 (29-30) (2010)
Alexander Shen
Decomposition Complexity. JAC (2010)
Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin
Game interpretation of Kolmogorov complexity CoRR (2010)
Laurent Bienvenu, Adam R. Day, Ilya Mezhirov, Alexander Shen
Ergodic-Type Characterizations of Algorithmic Randomness. CiE (2010)
Alexander Shen
Algorithmic Information Theory and Foundations of Probability. RP (2009)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Fixed Point Theorem and Aperiodic Tilings. Bull. EATCS 97 (2009)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
High Complexity Tilings with Sparse Errors. ICALP (1) (2009)
Daniil Musatov, Andrei E. Romashchenko, Alexander Shen
Variations on Muchnik's Conditional Complexity Theorem CoRR (2009)
Daniil Musatov, Andrei E. Romashchenko, Alexander Shen
Variations on Muchnik's Conditional Complexity Theorem. CSR (2009)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Fixed-point tile sets and their applications CoRR (2009)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
Limit complexities revisited CoRR (2008)
Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Veraschagin
Limit complexities revisited. STACS (2008)
Laurent Bienvenu, Wolfgang Merkle, Alexander Shen
A Simple Proof of Miller-Yu Theorem. Fundam. Informaticae 83 (1-2) (2008)
Bruno Durand, Alexander Shen, Andrei E. Romashchenko
Fixed Point and Aperiodic Tilings. Electron. Colloquium Comput. Complex. 15 (030) (2008)
Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk
On-Line Probability, Complexity and Randomness. ALT (2008)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Fixed Point and Aperiodic Tilings. Developments in Language Theory (2008)
Bruno Durand, Andrei E. Romashchenko, Alexander Shen
Fixed Point and Aperiodic Tilings CoRR (2008)
Bruno Durand, Leonid A. Levin, Alexander Shen
Complex tilings. J. Symb. Log. 73 (2) (2008)
Vladimir Vovk, Alexander Shen
Prequential Randomness. ALT (2008)
Laurent Bienvenu, Andrei E. Romashchenko, Alexander Shen
Sparse sets. JAC (2008)
Andrej Muchnik, Alexey V. Chernov, Alexander Shen
Algorithmic randomness and splitting of supermartingales CoRR (2008)
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. 28 (1) (2007)

Alexander Shen.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Alexander Shen