Alexander SHEN

Researcher at the Laboratory since February 2005

Permanent place of employment:

LIF Marseille and Institute for Information Transmission Problems, Moscow, Russia.

E-mail: alexander.shen AT lif.univ-mrs.fr, sasha.shen AT gmail.com

General

Personal

Born 31.12.1958 in Moscow, Russia.

Current affiliation

Institute for Information Transmission Problems, senior researcher

Current Research area

Kolmogorov complexity, algorithmic information theory

Other activities

Teaching (mathematics, computer science): Independent University of Moscow, Moscow State University, Moscow mathematical school No 57.

Column editor in Mathematical Intelligencer, 1999-2001.

Conference contributions

III Turing days, Bilgi University, Istanbul

Kolmogorov memorial conference, Moscow.

IEEE Conference on Computational Complexity, Aarhus (Denmark), ("Kolmogorov day")

Dagstuhl Seminar "Kolmogorov complexity and Applications", Schloß Dagstuhl, Germany

STOC ACM conference (with B.Durand, L.Levin)

IEEE conference on Computational Complexity (with A.Romashchenko, N.Vereshchagin)

STACS'99 (with B.Durand, N.Vereshchagin)

IEEE conference on Computational Complexity (with An.Muchnik, A.Romashchenko, N.Vereshchagin)

IEEE conference on Computational Complexity (with D.Hammer, A.Romashchenko, N.Vereshchagin)

SODA, ACM-SIAM (with K.Friedl, Z.Hatsagi)

Kolmogorov memorial conference, StPetersburg, Russia

Conference on Logical Foundations of Computer Science. Tver, Russia.

Second Congress of the Bernoulli Sosiety, Uppsala, invited talk

First Congress of the Bernoulli Sosiety, Tashkent, Uzbekistan

All-Union Conference on Logic and Methodology of Science, Lithuania, 1982.

6th All-Union Conference on Mathematical Logic, Tbilisi, Georgia.

International experience

Université de Provence, France. (Invited by Bruno Durand)

Dagstuhl-seminar "Kolmogorov complexity and its applications"

STINT professor, Uppsala University, Sweden. (Invited by Sergei Vorobyov)

Ecole Normale Superiore de Lyon, France. (Invited by Bruno Durand)

Rutgers University, USA. (Invited by Israel Gelfand)

Bonn University. (Invited by Marek Karpinski)

LABRI (Bordeaux), visiting scientist. (Invited by A.Zvonkine)

Instructor, Mathematics Department, Massachusetts Institute of Technology (spring term). (Invited by M.Sipser)

Seminars run

• Kolmogorov Seminar in Complexity of Description and Complexity of Computation (initiated by A.N.Kolmogorov, with A.L.Semenov and A.Kh.Shen), 1981--, graduate.
• seminar in Mathematical Logic and Algorithms Theory (with V.A.Uspensky, A.L.Semenov, A.Kh.Shen, A.A.Razborov), 1980--, undergraduate.
• courses on Kolmogorov complexity and randomness, complexity theory, finite automata, nonstandard analysis, algorithms design, first-order logic, algorithmic algebra, probability theory (at different years)

Recent Publications

Textbooks

1. A. Shen and N. Vereshchagin. Mathematical Logic and Computation Theory. Elements of Set Theory. Moscow Centre for Continuous Mathematical Education, 1999, 127 pages. (Russian)
   English translation: Basic Set Theory. American Mathematical Society. Student mathematical library, vol. 17. 2002
2. A. Shen and N. Vereshchagin. Mathematical Logic and Computation Theory. Computable Functions. Moscow Centre for Continuous Mathematical Education, 1999, 174 pages. (Russian)
   English translation: Computable functions. American Mathematical Society. Student mathematical library, vol. 19. 2003
3. A. Shen and N. Vereshchagin. Mathematical Logic and Computation Theory. Languages and Calculi. Moscow Centre for Continuous Mathematical Education, 1999, 286 pages. (Russian)
4. Algorithms and Programming (Russian editions: 1995, 2004; English: Birkhauser, 1997)
5. A. Kitaev, A. Shen, M.Vyalyi Classical and Quantum computations (Russian edition: MCCME publishers, English edition: AMS)

Refereed journal publications

1. A. Romashchenko, A. Shen, and N. Vereshchagin. "Combinatorial interpretation of Kolmogorov complexity", Theoretical Computer Science 271 (2002) 111--123. Preliminary version in: Proc. of 15th Annual IEEE Conference on Computational Complexity, Florence, July 2000, 131--137.
2. A. Chernov, An. Muchnik, A. Romashchenko, A. Shen, and N. Vereshchagin. Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theoretical Computer Science 271 (2002) 69--95. Preliminary version in: 14th Annual IEEE Conference on Computational Complexity, Atlanta, May 4-6, 1999, 114--122.
3. A. Shen and N. Vereshchagin. "Logical operations and Kolmogorov complexity". Theoretical Computer Science 271 (2002) 125--129.
4. D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin. "Inequalities for Shannon entropy and Kolmogorov complexity". Journal of Computer and Systems Sciences 60 (2000) 442-464.
5. B. Durand, A. Shen, and N. Vereshchagin. "Descriptive Complexity of Computable Sequences". Theoretical Computer Science 171 (2001), p. 47--58; Preliminary version: Proc. of 16th Ann. Symp. on Theoretical Aspects of Computer Science, Trier, Germany, March 1999, LNCS 1563, pp. 153--162.