Alexander Shen: Publications

Priority method and separation problems. Метод приоритета и проблемы отделения
- Doklady AN SSSR, 1979, 248, 6, 1309--1313. (Russian) MR81b:03046
pdf djvu

An axiomatic approach to algorithms theory and relativised computability.
Аксиоматический подход к теории алгоритмов и относительная вычислимость
- Vestnik MGU, ser. 1, 1980, 2, 27--29. (Russian) MR 82b:03087
pdf djvu

Some remark on non-integer numberings.
Некоторые замечания о нумерациях, не являющихся натуральными
- Matematicheskaja logika i matematicheskaja lingvistika. Kalinin, 1981. P. 162--165. (Russian)
MR 83k:03057
pdf ps djvu

Axiomatic description of the entropy notion for finite objects.
Аксиоматическое описания понятия энтропии для конечных объектов
VIII All-USSR conference ``Logika i metodologija nauki'', Vilnjus, 1982, p. 104--105. (Russian)
pdf ps djvu

The problem calculus and f0-spaces.
Исчисление задач и f0-пространства
VI All-USSR Conference on Math. Logic, Abstracts, Tbilisi, 1982, p. 204. (Russian)
pdf ps djvu

The frequency approach to the notion of random sequence.
Частотный подход к определению понятия случайной последовательности.
- Semiotika i informatika, M.:VINITI, 1982, 18, p. 14--42. (Russian)
pdf ps djvu

Понятие (&alpha,&beta)-стохастичности по Колмогорову и его свойства
Доклады Академии наук СССР, 271(6), 1337-1340.
pdf ps djvu
English translation: The concept of (&alpha,&beta)-stochasticity in the Kolmogorov sense, and its properties.
Soviet Math. Dokl., vol. 28 (1983), no.1, p.295--299. MR 85e:68034
pdf ps djvu

Towards the logical foundation of the applications of Probability Theory.
К логические основаниям применений теории вероятностей.
--- Semioticheskie aspekty formalizatsii intellektualnoi dejatelnosti, M., 1983, p.144-146 (Russian)

What is randomness?
Что такое случайность?
Квант, 1983, 7,.37-38. (Russian)
pdf ps djvu

Алгоритмические варианты понятия энтропии.
--- Doklady AN SSSR, 1984, 276, 3, 563--566. (Russian)
pdf ps djvu
English translation: Algorithmic variants of the notion of entropy
Soviet Math. Dokl, Vol. 29 (1984), no.3, p.569-573, MR 86f:94023
pdf ps djvu

Algorithmic variants of the notion of entropy. Ph.D. thesis. Алгоритмические варианты понятия энтропии. Диссертация на соискание учёной степени кандидата физико-математических наук. Москва, 1985. (Russian) pdf
Abstrast. Автореферат (Russian)
pdf ps djvu

One more definition of random sequence with respect to computable measure.
- First World Congress of the Bernoulli Society on Math. Statictics and Probability theory, Tashkent, 1986

L.L.Kontsevich, M.L.Kontsevich, A.Shen. Two algorithms of shape reconstruction.
- Avtometrija, 1987, 5, p. 72--77. (Russian)
English translation: Optoelectronics, instrumentation and data processing, 1987, no. 5, pp. 76--81

Commentary to Kolmogorov's paper on randomness. (Russian)
- In: A.N.Kolmogorov. Information theory and Algorithms Theory (Selected Papers) M., Nauka, 1987. MR 89a:01004

Computer Science (Informatika) in 9th grade of high school (Russian)
Informatika i Obrazovanie, 1987 (4), p. 20--30, (5), p. 24--31, (6), p. 17--27, 1988, (1), p. 8--15.
pdf ps djvu

Kogan A.G., Shen A. Teaching Programming in Mathematics School,
- In: Isuchenie osnov informatiki i vychislitelnoi techniki v srednei shkole, M., Prosvetschenie, 1987. (Russian)

Identity. Mathematical logic. (Articles for ``Small Mathematics Dictionary for children'')

Вероятностные стратегии в конечных играх с полной информацией.
- Теория вероятностей и её применения, 1987, 32, N 3, с. 567--569
Probabilistic strategies in games with full information.
- Theory of Probabilities and Its Applications, 1987, 32, N.3, p.567--569. (in Russian) MR 88m:90170
pdf ps djvu

A.P.Erschov, A.G.Kushnirenko, G.V.Lebedev, A.L.Semenov, A.Shen. Computer Literacy (Informatik). A textbook for high schools. Moscow, 1988

О соотношении между различными алгоритмическими определениями случайности.
- Доклады АН СССР, 1988, 302, 3, 548--552.
pdf djvu
Translation: On relations between different algorithmic definitions of randomness.
Soviet Math. Dokl., 38 (1989), 2, 316--319. MR 90c:68034
pdf djvu

Several chapters in "Programming: Simple and Difficult", Moscow, 1988
(With A.L.Semenov, A.G.Kogan a.o.)

Editor of the Russian translation (by N.Vereshchagin) of Paul Vitanyi and Ming Li paper "Kolmogorov complexity: twenty years later"
djvu

В.А.Успенский, А.Л.Семёнов, А.Шень, Может ли индивидуальная последовательность нулей и единиц быть случайной?
- Успехи математических наук, 1990, 45(1), 105--162.
pdf djvu
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
pdf djvu

Algorithmic complexity and randomness: recent developments. Second Congress of the Bernoulli Society.
(Invited talk on the Second Congress of Bernoulli Society.)
Russian translation: Алгоритмическая сложность и случайность: недавние достижения.
Теория вероятностей и её применения, 1992, 37(1), 124--131. MR1211211
djvu
Abstract of the talk.
pdf ps djvu

Patent: A device for checking the topology of connectors on a printed circuit (with coauthors) Moscow, 10 April, 1991.

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

[with A.K.Zvonkin, A.L.Semenov, S.K.Lando]
Algorithmics. Book for High School students (Russian) Institute of New Technologies, Moscow, 1992--1994. Reprinted later by "Drofa" publishing house (without permission)

Kolmogorov Complexity.
- Lecture Notes, Pereslavl, 1992.
tex

Анти-Тьюринг, или должна ли машина мыслить?
Научно-техническая информация, серия 2.
Информационные процессы и системы. 1992, 3, p. 17--19.
djvu
Translated in: Automatic documentation and Mathematical linguistics (1992), v. 26, no. 2, pp. 9--12.

Gelfand I.M., Shen A. Algebra (Textbook).
Birkhauser, 1993, 2nd printing, 1995, 3rd printing, 2000, 4th printing, 2002, 5th printing, 2003, 6th printing, 2004.
Русский вариант: Гельфанд И.М., Шень А. Алгебра. (Книга для школьников)
Москва. МЦНМО, 2-е изд., 2009
pdf

Comments to Kolmogorov's papers in: Kolmogorov A.N., Selected works of A.N.Kolmogorov, Vol.III. Edited by A.N.Shiryayev, translated from 1987 Russian original by A.B.Sossinsky, Kluwer Acad. Publ., Dordrecht, 1993 MR 95c:68096

Uspensky V.A., Shen A., Relations between varieties of Kolmogorov complexities.
Tech. Report CS-R9329, CWI, Netherlands, 1993
Final version: Math. Systems Theory, 29 (1996), N3, 271--292. MR 97c:68074
pdf

D.Hammer, A.Shen. A Strange Application of Kolmogorov Complexity.
Theory of Computing Systems, 31 (1998), no.1, 1--4. MR 99b:68103, Springer view link
(See also Tech.\ Report CS-R9328, CWI, Netherlands, 1993.)
pdf

K.Friedl, Z.Hatsagi, A.Shen, Low-degree tests
- Proc. of the Fifth ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), ACM, New York, 1994, p. 57--64. MR 95d:68055
pdf djvu

Shen' A., Entrance examination to the Mekh-Math,
Math.Intelligencer, 16 (1994), no.4, 6-10. MR 1294993
pdf

Программирование: теоремы и задачи.
Частично опубликован в журнале "Информатика и образование" в 1994 году. Первое издание: МЦНМО, 1995. Второе издание, исправленное и дополненное: МЦНМО, 2004. Третье издание: МЦНМО, 2007.
pdf
English version: "Algorithms and Programming: Problems and Solutions"
published by Birkhauser in 1997. 2nd ed. 2008 (Modern Classics, Birkhauser), 3rd ed. 2009 (Springer).

Semiinteger rectangles; Cube and Tetrahedron.
Math. Intelligencer, 19 (1997), no.1, p. 12-14.
pdf

Three-dimensional solutions for two-dimensional problems.
Math. Intelligencer, 19 (1997), no.3, 44-47; MR1475148
pdf

An unfair game. Colorings and coverings. Tilings and Polyhedra revisited.
Math. Intelligencer, 19 (1997), no.4, p. 48--50.
pdf

Probabilistic proofs
Math. Intelligencer, 20 (1998), no.3, 29--31, MR1646581
pdf

Two more probabilistic arguments. Poncelet theorem revisited.
Math. Intelligencer, 20 (1998), no.4, p. 30--32.
pdf

D.Hammer, A.Romashenko, A.Shen, N.Vereshchagin, Inequalities for Shannon entropies and Kolmogorov complexities.
Proceedings of Twelfth Annual IEEE Conference on Computational Complexity (Ulm, 1997). P.13--23. IEEE Computer Soc., Los Alamitos, CA, 1997. MR1758118.
Final version: Inequalities for Shannon entropy and Kolmogorov Complexity, Journal of Computer ans System Sciences, 2000, v.60, no.2, p.442--464; MR 2002e:68045
pdf

An.Muchnik, A.Romashchenko, N.Vereshagin, A.Shen, Upper semi-lattice of binary strings with relation "x is simple conditional to y".
DIMACS Tech. Report., 97-74 (December 1997)
Revised version: proceedings of 1999 Computational Complexity conference (Atlanta, GA, 1999), 114-122, IEEE Computer Soc., Los Alamitos, CA, 1999; MR1824585
Final version (with A. Chernov): TCS 271 (1--2), p. 69--95 (2002). MR: 2002m:68052 ps pdf

B.Durand, A.Shen, N.Vereshagin. Descriptive Complexity of Computable Sequences.
Proceedings of STACS'99 (Trier), Lecture notes in Computer Science, 1563, pp. 153--162, 1999. MR2000i:68080
ECCC-087, 2001;
Theoretical Computer Science, 271 (no. 1--2), p. 47--58 (2002); MR 2002k:68076
pdf

Unexpected proofs.
Math. Intelligencer, 21 (1999), no.3, p. 48--50.
pdf

Discussion on Kolmogorov Complexity and Statistical Analysis.
The Computer Journal, Vol. 42, No. 4, 1999, p. 340--342.
pdf ps

Lecture notes: Algorithmic Information Theory and Kolmogorov Complexity,
Uppsala University Technical Report 2000-034, December 2000. http://www.it.uu.se/research/reports/2000-034.
pdf

Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.
М. МЦНМО. 2008 (3-е изд.)
pdf
English version: N.Vereshchagin, A.Shen. Basic set theory.
Published by AMS, 2002. MR 2003f:03001

Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления.
(Part II. Languages and calculi. In Russian.)
М. МЦНМО. 2008 (3-е изд.)
pdf

Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.
М. МЦНМО. 2008 (3-е изд.)
pdf
English version: N.Vereshchagin, A.Shen. Computable functions.
Published by AMS, 2003. MR 2004b:03002

А.Китаев, М.Вялый, А.Шень. Классические и квантовые вычисления.
М.:МЦНМО, 1999
ps
С исправлениями: ps
English translation by Lester J. Senechal: A. Kitaev, M. Vyalyi, A. Shen. Classical and quantum computations.
AMS, RI, 2002. NR2003e:81004

A Cultural Gap Revisited. Why Circles?
Math. Intelligencer, 22 (2000), no. 2, p. 16--18.
pdf

Lights Out.
Math. Intelligencer, 22 (2000), no. 3, p. 20--21.
pdf

Cliques, the Cauchy Inequality, and Information Theory.
Math. Intelligencer, 22 (2000), no. 4, p. 14--15.
pdf

Задачи по математике, предлагавшиеся ученикам математического класса 57 школы (выпуск 2000 года, класс В).
М.:МЦНМО, 2000.
pdf ps
(Editor) Mathematical Problems Given to the Students of 57th Moscow School (graduated in 2000)
Moscow, MCCME Publishers, 2000. (Russian)

A. Shen, N. Vereshchagin: Logical operations and Kolmogorov complexity
ECCC-088, 2001;
ps pdf
Theoretical Computer Science, 271 (1--2), p. 125--129 (2002) MR 2002k:68080

B.Durand, L.A.Levin, A.Shen. Complex tilings.
Proceedings of the 33rd Annual ACM STOC 2001, 732--739. MR:2120376
http://arxiv.org/ps/cs.CC/0107008
pdf
Journal of Symbolic Logic, 73 (2), 2007, p. 593--613.

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.
pdf
TCS 271 (1--2): p. 111--123 (2002). MR 2003d:68104

Математическая индукция. М.:МЦНМО, 2004. 3-е изд., 2008
pdf
Mathematical induction. A popular exposition.
Moscow, MCCME publishers, 2004.

Логарифм и экспонента. М.:МЦНМО, 2005.
pdf
Logarithms and exponents. A popular exposition.
Moscow, MCCME publishers, 2005.

Простые и составные числа. М.:МЦНМО, 2005. 2-е изд., 2008
pdf
Prime and composite numbers.
Moscow, MCCME publishers, 2005.

Russian Encyclopedia. Articles on mathematical logic and computer science.

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.
pdf
Theoretical Computer Science, 2007, 384 (1), 77--86.

Universality in the theory of algorithms and computer science.
A talk given at Turing Days Conference, 2004, Istanbul.
pdf

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
pdf

Noga Alon, Ilan Newman, Alexander Shen, Gabor Tardos, Nikolai Vereshchagin. Partitioning multi-dimensional sets in a small number of ``uniform'' parts.
ECCC Report, TR05-95,
pdf
European Journal of Combinatorics, Volume 28, Issue 1, January 2007, p. 134--144. doi:10.1016/j.ejc.2005.08.002 MR2261810

Multisource information theory
ECCC Report, TR06-006.
Also published: Dagstuhl seminar 06051, http://drops.dagstuhl.de/opus/volltexte/2006/626
pdf
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
talk slides (djvu)

Combinatorial proof of Muchnik's theorem.
Dagstuhl seminar 06051, http://drops.dagstuhl.de/opus/volltexte/2006/625
Extended version: D.Musatov, A.Romashchenko, A.Shen, Variations on Muchnik's Conditional Complexity Theorem
Computer Science in Russia, 2009.
pdf

О "математической строгости" и школьном курсе математики.
М.:МЦНМО, 2006. 72с. ISBN 5-94057-254-5
A.Shen, "Mathematical rigour" and high-school mathematics. (In Russian).
pdf

What is Kolmogorov complexity, talk on the biology workshop organized by Poncelet Laboratory, 2006.
pdf

Игры и стратегии.
М.:МЦНМО, 2007. 2-е издание, 2008
Games and strategies (Russian).
pdf

Вероятность: примеры и задачи.
М.:МЦНМО, 2007. 2-е издание, 2008
Probability theory: Examples and Problems (Russian).
pdf

Laurent Bienvenu, Wolfgang Merkle, Alexander Shen. A simple proof of Miller--Yu theorem.
pdf
Fundamenta Informaticae, vol. 83, no. 1--2 (2008), p.21-24.

Laurent Bienvenu, Andrei Muchnik, Alexander Shen, Nikolay Vereshchagin. Limit complexities revisited.
Proceedings of STACS 2008 conference, p.73-84, http://drops.dagstuhl.de/opus/volltexte/2008/1335
pdf
Theory of Computing Systems, DOI 10.1007/s00224-009-9203-9, 17 March 2009.

Bruno Durand, Andrei Romashchenko, Alexander Shen. Fixed Point and Aperiodic Tilings.
Proceedings of 12th International Conference ``Developments in Language Theory'' (DLT), 2008, Lecture Notes in Computer in Science, vol. 5257, Springer-Verlag, 2008. pp. 276-288.
HAL pdf
see also arXiv:0802.2432

Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Sparse sets.
Journees Automates Cellulaires, 2008 (Uzes) pp. 18--28.
HAL pdf
(Later M.Raskin showed that there are two computable measures that are marginal distribution of some noncomputable measure, but are not marginal distributions of any computable measure, answering the question posed in the paper.)

Alexey Chernov, Alexander Shen, Nikolai Vereshchagin, Vladimir Vovk, 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.
pdf
talk slides pdf

Vladimir Vovk, Alexander Shen, Prequential Randomness,
Algorithmic Learning Theory, 19th International Conference (ALT 2008), Budapest, Hungary, Oct. 13--16, 2008, p.~154--168.
pdf

A.Chernov, A.Shen (editors), A.Muchnik, 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.

Bruno Durand, Andrei Romashchenko, Alexander Shen, Fixed point theorem and aperiodic tilings,
Bulletin of the EATCS, no. 97, pp. 126-136 (The Logic in Computer Science Column by Yuri Gurevich)
pdf

Laurent Bienvenu, Alexander Shen, Algorithmic information theory and martingales. [A historic account]
arxiv 0906.2614

Laurent Bienvenu, Glenn Shafer, Alexander Shen, On the history of martingales in the study of randomness,
Accepted by the Journal Elecronique d'Histoire des Probabilites et de la Statistique, ISSN 1773-0074.
pdf

Alexander Shen, Algorithmic Information Theory and Foundations of Probability.
arxiv 0906.4411

Bruno Durand, Andrei Romashchenko, Alexander Shen, High Complexity Tilings with Sparse Errors,
Accepted by ICALP 2009 conference.
pdf

Cling-Lueh Chang, Yuh-Danh Lyuu, Yen-Wu Ti, Alexander Shen
Sets of k-independent strings
Accepted by International Journal of the Foundations of Computer Science, Nov. 2009

Bruno Durand, Andrei Romashchenko, Alexander Shen:
Fixed-point tile sets and their applications
hal-00424024, arxiv:0910.2415

Космография
М.:МЦНМО, 2009.
Cosmography (Russian).
pdf

Recent papers can be found also in the NAFIT grant progress report