Alexander Shen

According to our database1, Alexander Shen authored at least 83 papers between 1991 and 2021.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



Automatic Kolmogorov complexity, normality, and finite-state dimension revisited.
J. Comput. Syst. Sci., 2021

On the Structure of Ammann A2 Tilings.
Discret. Comput. Geom., 2020

Inequalities for space-bounded Kolmogorov complexity.
CoRR, 2020

Complexity of majorants.
CoRR, 2020

Randomness Tests: Theory and Practice.
Proceedings of the Fields of Logic and Computation III, 2020

Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Two Characterizations of Finite-State Dimension.
Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

Dimension 1 sequences are close to randoms.
Theor. Comput. Sci., 2018

Algorithmic identification of probabilities is hard.
J. Comput. Syst. Sci., 2018

Axiomatic approach to the theory of algorithms and relativized computability.
CoRR, 2018

Information Distance Revisited.
CoRR, 2018

Plain Stopping Time and Conditional Complexities Revisited.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Algorithms and Geometric Constructions.
Proceedings of the Sailing Routes in the World of Computation, 2018

Layerwise Computability and Image Randomness.
Theory Comput. Syst., 2017

Conditional Probabilities and van Lambalgen's Theorem Revisited.
Theory Comput. Syst., 2017

Automatic Kolmogorov Complexity and Normality Revisited.
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

Compressibility and Probabilistic Proofs.
Proceedings of the Unveiling Dynamics and Complexity, 2017

Algorithmic Statistics: Forty Years Later.
Proceedings of the Computability and Complexity, 2017

Generic algorithms for halting problem and optimal machines revisited.
Log. Methods Comput. Sci., 2016

Geometry in Problems.
MSRI Mathematical Circles Library 18, American Mathematical Society, ISBN: 978-1-4704-3011-5, 2016

Topological Arguments for Kolmogorov Complexity.
Theory Comput. Syst., 2015

Algorithmic statistics revisited.
CoRR, 2015

Around Kolmogorov complexity: basic notions and results.
CoRR, 2015

What Percentage of Programs Halt?
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

<i>K</i>-trivial, <i>K</i>-low and <i>MLR</i>-low Sequences: A Tutorial.
Proceedings of the Fields of Logic and Computation II, 2015

Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity.
J. Symb. Log., 2014

Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma.
Fundam. Informaticae, 2014

K-trivial, K-low and MLR-low sequences: a tutorial.
CoRR, 2014

The axiomatic power of Kolmogorov complexity.
Ann. Pure Appl. Log., 2014

Algorithmic Identification of Probabilities Is Hard.
Proceedings of the Algorithmic Learning Theory - 25th International Conference, 2014

An Additivity Theorem for Plain Kolmogorov Complexity.
Theory Comput. Syst., 2013

Fixed-point tile sets and their applications.
J. Comput. Syst. Sci., 2012

A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points.
Inf. Comput., 2012

Limit complexities revisited [once more]
CoRR, 2012

Game Arguments in Computability Theory and Algorithmic Information Theory.
Proceedings of the How the World Computes, 2012

Random Semicomputable Reals Revisited.
Proceedings of the Computation, Physics and Beyond, 2012

Not every domain of a plain decompressor contains the domain of a prefix-free one.
Theor. Comput. Sci., 2011

Variations on Muchnik's Conditional Complexity Theorem.
Theory Comput. Syst., 2011

An additivity theorem for plain complexity
CoRR, 2011

Are random axioms useful?
CoRR, 2011

Algorithmic tests and randomness with respect to a class of measures
CoRR, 2011

Kolmogorov Complexity as a Language.
Proceedings of the Computer Science - Theory and Applications, 2011

Prequential randomness and probability.
Theor. Comput. Sci., 2010

Limit Complexities Revisited.
Theory Comput. Syst., 2010

Sets of k-Independent Strings.
Int. J. Found. Comput. Sci., 2010

Game interpretation of Kolmogorov complexity
CoRR, 2010

Decomposition Complexity.
Proceedings of the Second Symposium on Cellular Automata "Journées Automates Cellulaires", 2010

1D Effectively Closed Subshifts and 2D Tilings.
Proceedings of the Second Symposium on Cellular Automata "Journées Automates Cellulaires", 2010

Ergodic-Type Characterizations of Algorithmic Randomness.
Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

Effective Closed Subshifts in 1D Can Be Implemented in 2D.
Proceedings of the Fields of Logic and Computation, 2010

Algorithms and Programming - Problems and Solutions, Second Edition.
Springer undergraduate texts in mathematics and technology, Springer, ISBN: 978-1-4419-1747-8, 2010

Fixed Point Theorem and Aperiodic Tilings.
Bull. EATCS, 2009

Algorithmic Information Theory and Foundations of Probability.
Proceedings of the Reachability Problems, 3rd International Workshop, 2009

High Complexity Tilings with Sparse Errors.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Complex tilings.
J. Symb. Log., 2008

A Simple Proof of Miller-Yu Theorem.
Fundam. Informaticae, 2008

Fixed Point and Aperiodic Tilings.
Electron. Colloquium Comput. Complex., 2008

Algorithmic randomness and splitting of supermartingales
CoRR, 2008

Limit complexities revisited.
Proceedings of the STACS 2008, 2008

Sparse sets.
Proceedings of the First Symposium on Cellular Automata "Journées Automates Cellulaires" (JAC 2008), 2008

Prequential Randomness.
Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

On-Line Probability, Complexity and Randomness.
Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

Non-reducible descriptions for conditional Kolmogorov complexity.
Theor. Comput. Sci., 2007

Partitioning multi-dimensional sets in a small number of "uniform" parts.
Eur. J. Comb., 2007

Multisource algorithmic information theory
Electron. Colloquium Comput. Complex., 2006

Combinatorial proof of Muchnik's theorem.
Proceedings of the Kolmogorov Complexity and Applications, 29.01. - 03.02.2006, 2006

Non-reducible descriptions for conditional Kolmogorov complexity
Electron. Colloquium Comput. Complex., 2004

Logical operations and Kolmogorov complexity.
Theor. Comput. Sci., 2002

Combinatorial interpretation of Kolmogorov complexity.
Theor. Comput. Sci., 2002

Descriptive complexity of computable sequences.
Theor. Comput. Sci., 2002

Upper semi-lattice of binary strings with the relation "x is simple conditional to y".
Theor. Comput. Sci., 2002

Basic set theory.
Student mathematical library 17, American Mathematical Society, ISBN: 978-0-8218-2731-4, 2002

Inequalities for Shannon Entropy and Kolmogorov Complexity.
J. Comput. Syst. Sci., 2000

Discussion on Kolmogorov Complexity and Statistical Analysis.
Comput. J., 1999

Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

A Strange Application of Kolmogorov Complexity.
Theory Comput. Syst., 1998

Inequalities for Shannon entropies and Kolmogorov complexities.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Algorithms and programming - problems and solutions.
Birkhäuser, ISBN: 978-0-8176-3847-4, 1997

Relations Between Varieties of Kolmogorov Complexities.
Math. Syst. Theory, 1996

Low-degree Tests.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Birkhäuser, ISBN: 978-0-8176-3677-7, 1993

IP = PSPACE: Simplified Proof.
J. ACM, 1992

Simulation and Experimental Studies on the Concept of a Rate-Adaptive Digital Subscriber Loop (RA-DSL).
IEEE J. Sel. Areas Commun., 1991