Alexander Shen

139 papers A* 3A 6B 6C 9Misc 2Journal 95Unranked 13

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Vladimir V'yugin: Short biography and some research contributions. Inf. Comput. Péter Gács, Yuri Kalnishkan, Alexander Shen, Vladimir Vovk
2025	J	`jnl`	All Kolmogorov complexity functions are optimal, but are some more optimal? CoRR Bruno Bauwens, Alexander Kozachinskiy, Alexander Shen
2025	J	`jnl`	Bishop's (up)crossing inequality and lower semicomputable random reals revisited. CoRR Mikhail Andreev, Alexander Shen
2025	J	`jnl`	Conditional normality and finite-state dimensions revisited. Theor. Comput. Sci. Alexander Shen
2025	J	`jnl`	Ergodic theorem and algorithmic randomness (following V. V'yugin). Inf. Comput. Alexander Shen
2025	J	`jnl`	Local obstructions in sequences revisited. CoRR Matthieu Rosenfeld, Alexander Shen
2025	A*	`conf`	Optimal Bounds for Dissatisfaction in Perpetual Voting. AAAI Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
2025	J	`jnl`	Optimal bounds for dissatisfaction in perpetual voting. CoRR Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
2024	J	`jnl`	Conditional normality and finite-state dimensions revisited. CoRR Alexander Shen
2024	C	`conf`	Kolmogorov Complexity as a Combinatorial Tool. CiE Alexander Shen
2024	J	`jnl`	Kolmogorov complexity as a combinatorial tool. CoRR Alexander Shen
2023	J	`jnl`	Approximating Kolmogorov complexity. Comput. Ruslan Ishkuvatov, Daniil Musatov, Alexander Shen
2023	C	`conf`	Inequalities for Entropies and Dimensions. CiE Alexander Shen
2023	J	`jnl`	Taming randomness and complexity - Essays in honour of Professor Péter Gács. Theor. Comput. Sci. Ilir Çapuni, Jarkko Kari, Alexander Shen
2023	J	`jnl`	The Kraft-Barmpalias-Lewis-Pye lemma revisited. CoRR Alexander Shen
2023	J	`jnl`	The Kučera-Gács theorem revisited by Levin. Theor. Comput. Sci. George Barmpalias, Alexander Shen
2022	J	`jnl`	27 Open Problems in Kolmogorov Complexity. CoRR Andrei Romashchenko, Alexander Shen, Marius Zimand
2022	J	`jnl`	Individual codewords. Theor. Comput. Sci. Alexander Shen
2022	J	`jnl`	Inequalities for entropies and dimensions. CoRR Alexander Shen
2022	J	`jnl`	Inequalities for space-bounded Kolmogorov complexity. Comput. Bruno Bauwens, Péter Gács, Andrei Romashchenko, Alexander Shen
2021	J	`jnl`	27 Open Problems in Kolmogorov Complexity. SIGACT News Andrei Romashchenko, Alexander Shen, Marius Zimand
2021	J	`jnl`	Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. J. Comput. Syst. Sci. Alexander Kozachinskiy, Alexander Shen
2021	J	`jnl`	Gács-Kučera's Theorem Revisited by Levin. CoRR Alexander Shen
2021	J	`jnl`	Individual codewords. CoRR Alexander Shen
2020	J	`jnl`	Complexity of majorants. CoRR Alexander Shen
2020	J	`jnl`	Inequalities for space-bounded Kolmogorov complexity. CoRR Péter Gács, Andrei Romashchenko, Alexander Shen
2020	J	`jnl`	On the Structure of Ammann A2 Tilings. Discret. Comput. Geom. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
2020	—	`conf`	Randomness Tests: Theory and Practice. Fields of Logic and Computation III Alexander Shen
2019	A	`conf`	Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. STACS Gleb Posobin, Alexander Shen
2019	B	`conf`	Two Characterizations of Finite-State Dimension. FCT Alexander Kozachinskiy, Alexander Shen
2018	J	`jnl`	Algorithmic identification of probabilities is hard. J. Comput. Syst. Sci. Laurent Bienvenu, Santiago Figueira, Benoit Monin, Alexander Shen
2018	C	`conf`	Algorithms and Geometric Constructions. CiE Vladimir Uspenskiy, Alexander Shen
2018	J	`jnl`	Axiomatic approach to the theory of algorithms and relativized computability. CoRR Alexander Shen
2018	J	`jnl`	Dimension 1 sequences are close to randoms. Theor. Comput. Sci. Noam Greenberg, Joseph S. Miller, Alexander Shen, Linda Brown Westrick
2018	J	`jnl`	Information Distance Revisited. CoRR Bruno Bauwens, Alexander Shen
2018	B	`conf`	Plain Stopping Time and Conditional Complexities Revisited. MFCS Mikhail Andreev, Gleb Posobin, Alexander Shen
2018	J	`jnl`	Random noise increases Kolmogorov complexity and Hausdorff dimension. CoRR Gleb Posobin, Alexander Shen
2017	—	`conf`	Algorithmic Statistics: Forty Years Later. Computability and Complexity Nikolay K. Vereshchagin, Alexander Shen
2017	B	`conf`	Automatic Kolmogorov Complexity and Normality Revisited. FCT Alexander Shen
2017	J	`jnl`	Automatic Kolmogorov complexity and normality revisited. CoRR Alexander Shen
2017	C	`conf`	Compressibility and Probabilistic Proofs. CiE Alexander Shen
2017	J	`jnl`	Compressibility and probabilistic proofs. CoRR Alexander Shen
2017	J	`jnl`	Conditional Probabilities and van Lambalgen's Theorem Revisited. Theory Comput. Syst. Bruno Bauwens, Alexander Shen, Hayato Takahashi
2017	J	`jnl`	Dimension 1 sequences are close to randoms. CoRR Noam Greenberg, Joseph S. Miller, Alexander Shen, Linda Brown Westrick
2017	J	`jnl`	Layerwise Computability and Image Randomness. Theory Comput. Syst. Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
2017	J	`jnl`	Plain stopping time and conditional complexities revisited. CoRR Mikhail Andreev, Gleb Posobin, Alexander Shen
2016	J	`jnl`	Algorithmic statistics: forty years later. CoRR Nikolai K. Vereshchagin, Alexander Shen
2016	J	`jnl`	Generic algorithms for halting problem and optimal machines revisited. Log. Methods Comput. Sci. Laurent Bienvenu, Damien Desfontaines, Alexander Shen
2016	—	`book`	Geometry in Problems. Alexander Shen
2016	J	`jnl`	Layerwise computability and image randomness. CoRR Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
2015	J	`jnl`	Algorithmic statistics revisited. CoRR Nikolai K. Vereshchagin, Alexander Shen
2015	J	`jnl`	Around Kolmogorov complexity: basic notions and results. CoRR Alexander Shen
2015	J	`jnl`	Topological Arguments for Kolmogorov Complexity. Theory Comput. Syst. Andrei Romashchenko, Alexander Shen
2015	—	`conf`	What Percentage of Programs Halt? ICALP (1) Laurent Bienvenu, Damien Desfontaines, Alexander Shen
2014	B	`conf`	Algorithmic Identification of Probabilities Is Hard. ALT Laurent Bienvenu, Benoit Monin, Alexander Shen
2014	J	`jnl`	Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity. J. Symb. Log. Bruno Bauwens, Alexander Shen
2014	J	`jnl`	K-trivial, K-low and MLR-low sequences: a tutorial. CoRR Laurent Bienvenu, Alexander Shen
2014	J	`jnl`	Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma. Fundam. Informaticae Andrei Yu. Rumyantsev, Alexander Shen
2014	J	`jnl`	The axiomatic power of Kolmogorov complexity. Ann. Pure Appl. Log. Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren
2013	J	`jnl`	An Additivity Theorem for Plain Kolmogorov Complexity. Theory Comput. Syst. Bruno Bauwens, Alexander Shen
2013	J	`jnl`	Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma CoRR Andrei Yu. Rumyantsev, Alexander Shen
2013	J	`jnl`	The axiomatic power of Kolmogorov complexity CoRR Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren
2012	J	`jnl`	A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points. Inf. Comput. Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, Alexander Shen
2012	J	`jnl`	Fixed-point tile sets and their applications. J. Comput. Syst. Sci. Bruno Durand, Andrei Romashchenko, Alexander Shen
2012	C	`conf`	Game Arguments in Computability Theory and Algorithmic Information Theory. CiE Alexander Shen
2012	J	`jnl`	Game arguments in computability theory and algorithmic information theory CoRR Alexander Shen
2012	J	`jnl`	Limit complexities revisited [once more] CoRR Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
2012	—	`conf`	Random Semicomputable Reals Revisited. Computation, Physics and Beyond Laurent Bienvenu, Alexander Shen
2012	—	`conf`	Topological arguments for Kolmogorov complexity AUTOMATA & JAC Alexander Shen, Andrei Romashchenko
2011	J	`jnl`	Algorithmic tests and randomness with respect to a class of measures CoRR Laurent Bienvenu, Péter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen
2011	J	`jnl`	An additivity theorem for plain complexity CoRR Bruno Bauwens, Alexander Shen
2011	J	`jnl`	Are random axioms useful? CoRR Alexander Shen
2011	Misc	`conf`	Kolmogorov Complexity as a Language. CSR Alexander Shen
2011	J	`jnl`	Kolmogorov complexity as a language CoRR Alexander Shen
2011	J	`jnl`	Not every domain of a plain decompressor contains the domain of a prefix-free one. Theor. Comput. Sci. Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen
2011	J	`jnl`	Variations on Muchnik's Conditional Complexity Theorem. Theory Comput. Syst. Daniil Musatov, Andrei Romashchenko, Alexander Shen
2010	J	`jnl`	1D Effectively Closed Subshifts and 2D Tilings CoRR Bruno Durand, Alexander Shen, Andrei Romashchenko
2010	—	`conf`	1D Effectively Closed Subshifts and 2D Tilings. JAC Bruno Durand, Andrei Romashchenko, Alexander Shen
2010	J	`jnl`	A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points CoRR Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, Alexander Shen
2010	—	`book`	Algorithms and Programming - Problems and Solutions, Second Edition. Alexander Shen
2010	J	`jnl`	Decomposition Complexity CoRR Alexander Shen
2010	—	`conf`	Decomposition Complexity. JAC Alexander Shen
2010	—	`conf`	Effective Closed Subshifts in 1D Can Be Implemented in 2D. Fields of Logic and Computation Bruno Durand, Andrei Romashchenko, Alexander Shen
2010	J	`jnl`	Effective closed subshifts in 1D can be implemented in 2D CoRR Bruno Durand, Andrei Romashchenko, Alexander Shen
2010	C	`conf`	Ergodic-Type Characterizations of Algorithmic Randomness. CiE Laurent Bienvenu, Adam R. Day, Ilya Mezhirov, Alexander Shen
2010	J	`jnl`	Fixed point theorem and aperiodic tilings CoRR Bruno Durand, Andrei Romashchenko, Alexander Shen
2010	J	`jnl`	Game interpretation of Kolmogorov complexity CoRR Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin
2010	J	`jnl`	Limit Complexities Revisited. Theory Comput. Syst. Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
2010	J	`jnl`	Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One CoRR Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen
2010	J	`jnl`	Prequential randomness and probability. Theor. Comput. Sci. Vladimir Vovk, Alexander Shen
2010	J	`jnl`	Sets of k-Independent Strings. Int. J. Found. Comput. Sci. Yen-Wu Ti, Ching-Lueh Chang, Yuh-Dauh Lyuu, Alexander Shen
2009	—	`conf`	Algorithmic Information Theory and Foundations of Probability. RP Alexander Shen
2009	J	`jnl`	Fixed Point Theorem and Aperiodic Tilings. Bull. EATCS Bruno Durand, Andrei Romashchenko, Alexander Shen
2009	J	`jnl`	Fixed-point tile sets and their applications CoRR Bruno Durand, Andrei Romashchenko, Alexander Shen
2009	—	`conf`	High Complexity Tilings with Sparse Errors. ICALP (1) Bruno Durand, Andrei Romashchenko, Alexander Shen
2009	J	`jnl`	Variations on Muchnik's Conditional Complexity Theorem CoRR Daniil Musatov, Andrei Romashchenko, Alexander Shen
2009	Misc	`conf`	Variations on Muchnik's Conditional Complexity Theorem. CSR Daniil Musatov, Andrei Romashchenko, Alexander Shen
2008	J	`jnl`	A Simple Proof of Miller-Yu Theorem. Fundam. Informaticae Laurent Bienvenu, Wolfgang Merkle, Alexander Shen
2008	J	`jnl`	Algorithmic randomness and splitting of supermartingales CoRR Andrej Muchnik, Alexey V. Chernov, Alexander Shen
2008	J	`jnl`	Complex tilings. J. Symb. Log. Bruno Durand, Leonid A. Levin, Alexander Shen
2008	J	`jnl`	Fixed Point and Aperiodic Tilings CoRR Bruno Durand, Andrei Romashchenko, Alexander Shen
2008	C	`conf`	Fixed Point and Aperiodic Tilings. Developments in Language Theory Bruno Durand, Andrei Romashchenko, Alexander Shen
2008	J	`jnl`	Fixed Point and Aperiodic Tilings. Electron. Colloquium Comput. Complex. Bruno Durand, Alexander Shen, Andrei Romashchenko
2008	J	`jnl`	Limit complexities revisited CoRR Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin
2008	A	`conf`	Limit complexities revisited. STACS Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Veraschagin
2008	B	`conf`	On-Line Probability, Complexity and Randomness. ALT Alexey V. Chernov, Alexander Shen, Nikolai K. Vereshchagin, Vladimir Vovk
2008	B	`conf`	Prequential Randomness. ALT Vladimir Vovk, Alexander Shen
2008	—	`conf`	Sparse sets. JAC Laurent Bienvenu, Andrei Romashchenko, Alexander Shen
2007	J	`jnl`	Non-reducible descriptions for conditional Kolmogorov complexity. Theor. Comput. Sci. Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin
2007	J	`jnl`	Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2006	—	`conf`	Combinatorial proof of Muchnik's theorem. Kolmogorov Complexity and Applications Alexander Shen
2006	—	`conf`	Multisource Algorithmic Information Theory. Kolmogorov Complexity and Applications Alexander Shen
2006	C	`conf`	Multisource Algorithmic Information Theory. TAMC Alexander Shen
2006	J	`jnl`	Multisource algorithmic information theory Electron. Colloquium Comput. Complex. Alexander Shen
2006	C	`conf`	Non-reducible Descriptions for Conditional Kolmogorov Complexity. TAMC Andrej Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
2005	J	`jnl`	Partitioning multi-dimensional sets in a small number of "uniform" parts Electron. Colloquium Comput. Complex. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2004	J	`jnl`	Non-reducible descriptions for conditional Kolmogorov complexity Electron. Colloquium Comput. Complex. Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
2002	—	`book`	Basic set theory. Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Combinatorial interpretation of Kolmogorov complexity. Theor. Comput. Sci. Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Descriptive complexity of computable sequences. Theor. Comput. Sci. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Logical operations and Kolmogorov complexity. Theor. Comput. Sci. Alexander Shen, Nikolai K. Vereshchagin
2002	J	`jnl`	Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theor. Comput. Sci. Alexey V. Chernov, Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2001	J	`jnl`	Complex Tilings CoRR Bruno Durand, Leonid A. Levin, Alexander Shen
2001	A*	`conf`	Complex tilings. STOC Bruno Durand, Leonid A. Levin, Alexander Shen
2001	J	`jnl`	Descriptive complexity of computable sequences Electron. Colloquium Comput. Complex. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
2001	J	`jnl`	Logical operations and Kolmogorov complexity Electron. Colloquium Comput. Complex. Alexander Shen, Nikolai K. Vereshchagin
2000	J	`jnl`	Combinatorial Interpretation of Kolmogorov Complexity Electron. Colloquium Comput. Complex. Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000	A	`conf`	Combinatorial Interpretation of Kolmogorov Complexity. CCC Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
2000	J	`jnl`	Inequalities for Shannon Entropy and Kolmogorov Complexity. J. Comput. Syst. Sci. Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1999	A	`conf`	Descriptive Complexity of Computable Sequences. STACS Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin
1999	J	`jnl`	Discussion on Kolmogorov Complexity and Statistical Analysis. Comput. J. Alexander Shen
1999	A	`conf`	Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". CCC Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1998	J	`jnl`	A Strange Application of Kolmogorov Complexity. Theory Comput. Syst. Daniel Hammer, Alexander Shen
1997	—	`book`	Algorithms and programming - problems and solutions. Alexander Shen
1997	A	`conf`	Inequalities for Shannon entropies and Kolmogorov complexities. CCC Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
1996	J	`jnl`	Relations Between Varieties of Kolmogorov Complexities. Math. Syst. Theory Vladimir A. Uspensky, Alexander Shen
1994	A*	`conf`	Low-degree Tests. SODA Katalin Friedl, Zsolt Hátsági, Alexander Shen
1993	—	`book`	Algebra. Israel M. Gelfand, Alexander Shen
1992	J	`jnl`	IP = PSPACE: Simplified Proof. J. ACM Alexander Shen