Alexander Shen

CoRR, 2024

2023

Taming randomness and complexity - Essays in honour of Professor Péter Gács.

[BibT_eX]

[DOI]

Ilir Çapuni

Jarkko Kari

Theor. Comput. Sci., March, 2023

The Kučera-Gács theorem revisited by Levin.

[BibT_eX]

[DOI]

George Barmpalias

Theor. Comput. Sci., February, 2023

The Kraft-Barmpalias-Lewis-Pye lemma revisited.

[BibT_eX]

[DOI]

CoRR, 2023

Approximating Kolmogorov complexity.

[BibT_eX]

[DOI]

Ruslan Ishkuvatov

Daniil Musatov

Comput., 2023

Inequalities for Entropies and Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Unity of Logic and Computation, 2023

2022

Individual codewords.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Inequalities for space-bounded Kolmogorov complexity.

[BibT_eX]

[DOI]

Péter Gács

Comput., 2022

2021

27 Open Problems in Kolmogorov Complexity.

[BibT_eX]

[DOI]

Marius Zimand

SIGACT News, 2021

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited.

[BibT_eX]

[DOI]

Alexander Kozachinskiy

J. Comput. Syst. Sci., 2021

Gács-Kučera's Theorem Revisited by Levin.

[BibT_eX]

[DOI]

CoRR, 2021

2020

On the Structure of Ammann A2 Tilings.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

Inequalities for space-bounded Kolmogorov complexity.

[BibT_eX]

[DOI]

Péter Gács

CoRR, 2020

Complexity of majorants.

[BibT_eX]

[DOI]

CoRR, 2020

Randomness Tests: Theory and Practice.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation III, 2020

2019

Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension.

[BibT_eX]

[DOI]

Gleb Posobin

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Two Characterizations of Finite-State Dimension.

[BibT_eX]

[DOI]

Alexander Kozachinskiy

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

2018

Dimension 1 sequences are close to randoms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Algorithmic identification of probabilities is hard.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

Axiomatic approach to the theory of algorithms and relativized computability.

[BibT_eX]

[DOI]

CoRR, 2018

Information Distance Revisited.

[BibT_eX]

[DOI]

CoRR, 2018

Plain Stopping Time and Conditional Complexities Revisited.

[BibT_eX]

[DOI]

Mikhail Andreev

Gleb Posobin

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Algorithms and Geometric Constructions.

[BibT_eX]

[DOI]

Vladimir Uspenskiy

Proceedings of the Sailing Routes in the World of Computation, 2018

2017

Layerwise Computability and Image Randomness.

[BibT_eX]

[DOI]

Mathieu Hoyrup

Theory Comput. Syst., 2017

Conditional Probabilities and van Lambalgen's Theorem Revisited.

[BibT_eX]

[DOI]

Hayato Takahashi

Theory Comput. Syst., 2017

Automatic Kolmogorov Complexity and Normality Revisited.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

Compressibility and Probabilistic Proofs.

[BibT_eX]

[DOI]

Proceedings of the Unveiling Dynamics and Complexity, 2017

Algorithmic Statistics: Forty Years Later.

[BibT_eX]

[DOI]

Nikolay K. Vereshchagin

Proceedings of the Computability and Complexity, 2017

2016

Generic algorithms for halting problem and optimal machines revisited.

[BibT_eX]

[DOI]

Damien Desfontaines

Log. Methods Comput. Sci., 2016

Geometry in Problems.

[BibT_eX]

[DOI]

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

2015

Topological Arguments for Kolmogorov Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Algorithmic statistics revisited.

[BibT_eX]

[DOI]

CoRR, 2015

Around Kolmogorov complexity: basic notions and results.

[BibT_eX]

[DOI]

CoRR, 2015

What Percentage of Programs Halt?

[BibT_eX]

[DOI]

Damien Desfontaines

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

K-trivial, K-low and MLR-low Sequences: A Tutorial.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation II, 2015

2014

Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity.

[BibT_eX]

[DOI]

J. Symb. Log., 2014

Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma.

[BibT_eX]

[DOI]

Andrei Yu. Rumyantsev

Fundam. Informaticae, 2014

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

[BibT_eX]

[DOI]

CoRR, 2014

The axiomatic power of Kolmogorov complexity.

[BibT_eX]

[DOI]

Antoine Taveneaux

Stijn Vermeeren

Ann. Pure Appl. Log., 2014

Algorithmic Identification of Probabilities Is Hard.

[BibT_eX]

[DOI]

Benoit Monin

Proceedings of the Algorithmic Learning Theory - 25th International Conference, 2014

2013

An Additivity Theorem for Plain Kolmogorov Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

2012

Fixed-point tile sets and their applications.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

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

[BibT_eX]

[DOI]

Inf. Comput., 2012

Limit complexities revisited [once more]

[BibT_eX]

[DOI]

CoRR, 2012

Game Arguments in Computability Theory and Algorithmic Information Theory.

[BibT_eX]

[DOI]

Proceedings of the How the World Computes, 2012

Random Semicomputable Reals Revisited.

[BibT_eX]

[DOI]

Proceedings of the Computation, Physics and Beyond, 2012

2011

Not every domain of a plain decompressor contains the domain of a prefix-free one.

[BibT_eX]

[DOI]

Mikhail Andreev

Ilya P. Razenshteyn

Theor. Comput. Sci., 2011

Variations on Muchnik's Conditional Complexity Theorem.

[BibT_eX]

[DOI]

Daniil Musatov

Theory Comput. Syst., 2011

An additivity theorem for plain complexity

[BibT_eX]

[DOI]

CoRR, 2011

Are random axioms useful?

[BibT_eX]

[DOI]

CoRR, 2011

Algorithmic tests and randomness with respect to a class of measures

[BibT_eX]

[DOI]

CoRR, 2011

Kolmogorov Complexity as a Language.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Prequential randomness and probability.

[BibT_eX]

[DOI]

Vladimir Vovk

Theor. Comput. Sci., 2010

Limit Complexities Revisited.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Sets of k-Independent Strings.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2010

Game interpretation of Kolmogorov complexity

[BibT_eX]

[DOI]

Ilya Mezhirov

CoRR, 2010

Decomposition Complexity.

[BibT_eX]

[DOI]

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

1D Effectively Closed Subshifts and 2D Tilings.

[BibT_eX]

[DOI]

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

Ergodic-Type Characterizations of Algorithmic Randomness.

[BibT_eX]

[DOI]

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

Effective Closed Subshifts in 1D Can Be Implemented in 2D.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation, 2010

Algorithms and Programming - Problems and Solutions, Second Edition.

[BibT_eX]

[DOI]

Springer undergraduate texts in mathematics and technology, Springer, ISBN: 978-1-4419-1747-8, 2010

2009

Fixed Point Theorem and Aperiodic Tilings.

[BibT_eX]

Bull. EATCS, 2009

Algorithmic Information Theory and Foundations of Probability.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems, 3rd International Workshop, 2009

High Complexity Tilings with Sparse Errors.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Complex tilings.

[BibT_eX]

[DOI]

Leonid A. Levin

J. Symb. Log., 2008

A Simple Proof of Miller-Yu Theorem.

[BibT_eX]

[DOI]

Wolfgang Merkle

Fundam. Informaticae, 2008

Fixed Point and Aperiodic Tilings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Algorithmic randomness and splitting of supermartingales

[BibT_eX]

[DOI]

Alexey V. Chernov

CoRR, 2008

Limit complexities revisited.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

Sparse sets.

[BibT_eX]

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

Prequential Randomness.

[BibT_eX]

[DOI]

Vladimir Vovk

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

On-Line Probability, Complexity and Randomness.

[BibT_eX]

[DOI]

Alexey V. Chernov

Vladimir Vovk

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

2007

Non-reducible descriptions for conditional Kolmogorov complexity.

[BibT_eX]

[DOI]

Mikhail Ustinov

Michael V. Vyugin

Theor. Comput. Sci., 2007

Partitioning multi-dimensional sets in a small number of "uniform" parts.

[BibT_eX]

[DOI]

Eur. J. Comb., 2007

2006

Multisource algorithmic information theory

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Combinatorial proof of Muchnik's theorem.

[BibT_eX]

[DOI]

Proceedings of the Kolmogorov Complexity and Applications, 29.01. - 03.02.2006, 2006

2004

Non-reducible descriptions for conditional Kolmogorov complexity

[BibT_eX]

[DOI]

Andrei A. Muchnik

Michael V. Vyugin

Electron. Colloquium Comput. Complex., 2004

2002

Logical operations and Kolmogorov complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Combinatorial interpretation of Kolmogorov complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Descriptive complexity of computable sequences.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Upper semi-lattice of binary strings with the relation "x is simple conditional to y".

[BibT_eX]

[DOI]

Alexey V. Chernov

Andrei A. Muchnik

Theor. Comput. Sci., 2002

Basic set theory.

[BibT_eX]

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

2000

Inequalities for Shannon Entropy and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Daniel Hammer

J. Comput. Syst. Sci., 2000

1999

Discussion on Kolmogorov Complexity and Statistical Analysis.

[BibT_eX]

[DOI]

Comput. J., 1999

Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".

[BibT_eX]

[DOI]

Andrei A. Muchnik

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A Strange Application of Kolmogorov Complexity.

[BibT_eX]

[DOI]

Daniel Hammer

Theory Comput. Syst., 1998

1997

Inequalities for Shannon entropies and Kolmogorov complexities.

[BibT_eX]

[DOI]

Daniel Hammer

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Algorithms and programming - problems and solutions.

[BibT_eX]

Birkhäuser, ISBN: 978-0-8176-3847-4, 1997

1996

Relations Between Varieties of Kolmogorov Complexities.

[BibT_eX]

[DOI]

Vladimir A. Uspensky

Math. Syst. Theory, 1996

1994

Low-degree Tests.

[BibT_eX]

[DOI]

Katalin Friedl

Zsolt Hátsági

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

1993

Algebra.

[BibT_eX]

[DOI]

Israel M. Gelfand

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

1992

IP = PSPACE: Simplified Proof.

[BibT_eX]

[DOI]

J. ACM, 1992

1991

Simulation and Experimental Studies on the Concept of a Rate-Adaptive Digital Subscriber Loop (RA-DSL).

[BibT_eX]

[DOI]

Wayne D. Grover

Witold A. Krzymien