Alexander SHEN
Researcher
at the Laboratory since February 2005
Permanent
place of employment:
LIF Marseille and Institute for Information Transmission Problems,
Moscow, Russia.
Email: alexander.shen AT lif.univmrs.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, 19992001.
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, ACMSIAM (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
 AllUnion Conference on Logic and Methodology of
Science, Lithuania, 1982.
 6th AllUnion Conference on Mathematical Logic,
Tbilisi, Georgia.
International experience

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

Dagstuhlseminar "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, firstorder logic,
algorithmic algebra, probability theory (at different
years)
Recent Publications
Textbooks
 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
 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
 A. Shen and N. Vereshchagin. Mathematical Logic and Computation Theory.
Languages and Calculi.
Moscow Centre for Continuous Mathematical Education, 1999, 286 pages.
(Russian)
 Algorithms and Programming (Russian editions: 1995, 2004;
English: Birkhauser, 1997)
 A. Kitaev, A. Shen, M.Vyalyi
Classical and Quantum computations (Russian edition: MCCME publishers,
English edition: AMS)
Refereed journal publications

A. Romashchenko, A. Shen, and N. Vereshchagin.
"Combinatorial interpretation of Kolmogorov complexity",
Theoretical Computer Science 271 (2002) 111123.
Preliminary version in:
Proc. of 15th Annual IEEE Conference on Computational Complexity,
Florence, July 2000, 131137.

A. Chernov, An. Muchnik, A. Romashchenko, A. Shen, and N. Vereshchagin.
Upper semilattice of binary strings with the relation
"x is simple conditional to y".
Theoretical Computer Science 271 (2002) 6995.
Preliminary version in:
14th Annual IEEE Conference on Computational Complexity, Atlanta, May 46,
1999, 114122.

A. Shen and N. Vereshchagin.
"Logical operations and Kolmogorov complexity".
Theoretical Computer Science 271 (2002) 125129.

D. Hammer, A. Romashchenko,
A. Shen, and N. Vereshchagin.
"Inequalities for Shannon entropy and Kolmogorov complexity".
Journal of Computer and Systems Sciences 60 (2000) 442464.

B. Durand, A. Shen, and N. Vereshchagin.
"Descriptive Complexity of Computable Sequences".
Theoretical Computer Science 171 (2001), p. 4758;
Preliminary version: Proc. of 16th Ann. Symp. on
Theoretical Aspects of Computer Science, Trier, Germany, March
1999, LNCS 1563, pp. 153162.