A. Shen - Publications

2009

Shen A., Algorithmic Information Theory and Foundations of Probability Reachability Problems Third International Workshop, RP 2009, Palaiseau, France, September 23-25, 2009, Proceedings Lecture Notes in Computer Science Vol. 5797
Bienvenu L., Shafer G., Shen A., On the history of martingales in the study of randomness, Journal Elecronique d"Histoire des Probabilites et de la Statistique, ISSN 1773-0074.
Bienvenu L., Shen A., Algorithmic information theory and martingales. [A historic account] arxiv 0906.2614
Chernov A., Shen A., Muchnik An., Algorithmic randomness and splitting of supermartingales, arxiv 0807.3156 Проблемы передачи информации, 2009, 45:1, 60-70. English version: Problems of Information Transmission, 2009, 45:1, 54-64.
Bienvenu L., Muchnik An., Shen A., Verehshchagin N., Limit complexities revisited. Proceedings of STACS 2008 conference, p.73-84, http://drops.dagstuhl.de/opus/volltexte/2008/1335 Theory of Computing Systems, DOI 10.1007/s00224-009-9203-9, 17 March 2009. http://drops.dagstuhl.de/opus/volltexte/2008/1335

2008

Vereshchagin N., Shen A., English version: N.Vereshchagin, A.Shen. Computable functions. Published by AMS, 2003. MR 2004b:03002
Vereshchagin N., Shen A., English version: N.Vereshchagin, A.Shen. Basic set theory. Published by AMS, 2002. MR 2003f:03001
Bienvenu L., Merkle W., Shen A., A simple proof of Miller--Yu theorem. Fundamenta Informaticae, vol. 83, no. 1--2 (2008), p.21-24.
Vovk V., Shen A., Prequential Randomness, Algorithmic Learning Theory, 19th International Conference (ALT 2008), Budapest, Hungary, Oct. 13--16, 2008, p.~154--168.
Chernov A., Shen A., Vereshchagin N., Vovk V., On-line Probability, Complexity and Randomness. Algorithmic Learning Theory, 19th International Conference (ALT 2008), Budapest, Hungary, Oct. 13--16, 2008, Lecture Notes in Computer Science, v.~5254, p.~138--153.

2007

Shen A., Программирование: теоремы и задачи. Третье издание: МЦНМО, 2007. English version: "Algorithms and Programming: Problems and Solutions" published by Birkhauser in 1997. 2nd ed. 2008 (Modern Classics, Birkhauser), 3rd ed. 2009 (Springer).
Alon N., Newman I., Shen A., Tardos G., Vereshchagin N., Partitioning multi-dimensional sets in a small number of ``uniform"" parts. ECCC Report, TR05-95, European Journal of Combinatorics, Volume 28, Issue 1, January 2007, p. 134--144. doi:10.1016/j.ejc.2005.08.002 MR2261810
Shen A., A.Muchnik, A.Shen, N.Vereshchagin, M.Vyugin. Non-reducible descriptions for conditional Kolmogorov complexity. ECCC Report, TR04-054, Jun 29, 2004 See also: Theory and Applications of Models of Computation, Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 3959 (2006), p.308-317 (a talk given in Beijing conference, May 2006). MR2277252 Extended version: Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai Vereshchagin, Michael Vyugin, Non-reducible descriptions for conditional Kolmogorov complexity. Theoretical Computer Science, 2007, 384 (1), 77--86.

2006

Shen A., Multisource information theory ECCC Report, TR06-006. Also published: Dagstuhl seminar 06051, http://drops.dagstuhl.de/opus/volltexte/2006/626 See also: Theory and Applications of Models of Computation, Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 3959 (2006), p. 327-338. (a talk given in Beijing conference, May 2006). MR2277254

2005

Shen A., B.Durand, L.A.Levin, A.Shen. Local rules and global order, or Aperiodic Tilings. Mathematical Intelligencer, 2005, v. 27, no.1, p. 64-68. MR 2006c:52058

2002

Shen A., Vereshchagin N., Logical operations and Kolmogorov complexity ECCC-088, 2001; Theoretical Computer Science, 271 (1--2), p. 125--129 (2002) MR 2002k:68080
Shen A., A. Romashchenko, A. Shen, N. Vereshchagin, Combinatorial interpretation of Kolmogorov complexity, ECCC 7(26):2000; 15th Annual IEEE conference on Computational Complexity (Florence, 2000), 131-137, IEEE Computer Soc., Los Alamitos, CA, 2000; MR1823533. TCS 271 (1--2): p. 111--123 (2002). MR 2003d:68104

1992

Shen A., IP=PSPACE: simplified proof. Journal of the ACM, 39, no.4 (Oct. 1992), p. 878--880. MR 94j:68270

1990

Shen A., Translation: V.A.Uspensky, A.L.Semenov, A.Shen. Can a single sequence of zeros and ones be random? Russian Math. Surveys, 45:1 (1990), 121--189. MR 91f:03043

1985

Shen A., Algorithmic variants of the notion of entropy. Ph.D. thesis.