Nikolay VERESHCHAGIN

Researcher at the Laboratory since February 2005

Permanent place of employment:

Dept. of Mathematical Logic and Theory of Algorithms, Faculty of Mechanics and Mathematics, Moscow State University, Moscow, 119899 Russia.

FAX: +7 095 939 3031

E-mail: ver AT mech.math.msu.su

General

Personal

Born 27.10.1958 in Moscow, Russia.

Current affiliation

Professor at Lomonossov Moscow State University Faculty of Mechanics and Mathematics Department of Mathematical Logic and Theory of Algorithms

Current Research area

Computational complexity, Kolmogorov complexity

Other activities

Program committee member of 18th IEEE Conference on Computational Complexity, 2003, Aarhus (Denmark) and of

18th International Symposium on Theoretical Aspects of Computer Science, 2001, Dresden (Germany).

Conference contributions

2004

31st International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland

2005, 2004, 1999

Symposium on Theoretical Aspects of Computer Science, STACS

2002

47th IEEE Symposium on Foundations of Computer Science, FOCS.

2001, 2000, 1999, 1998, 1997, 1993, 1992

Annual IEEE Conference on Computational Complexity.

2003, 1996

Dagstuhl-seminars "Structure and Complexity" and "Kolmogorov complexity and Applications", Schloß Dagstuhl, Germany

1995

Eighth Annual Conference on Computational Learning Theory, Santa Cruz, CA, USA

1995

Third Israel Symposium on Theory of Computing and Systems, Tel-Aviv, Israel (Two talks)

1994

COLORET workshop, Amsterdam, the Netherlands

1992

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

1991

Suslin Memorial Conference. Saratov, Russia.

1988

9th All-Union Conference on Mathematical Logic, Leningrad, Russia.

1985

18th All-Union Algebraic Conference, Kishinev, Moldova

1982

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

International experience

2005, 2004, 2003, 2002, 2001

A month research visit to CWI, Amsterdam. Invited by H. Buhrman and P. Vitanyi.

2004, 2003, 2002, 2001, 2000

A month research visit to Université de Provence, France. Invited by Bruno Durand.

2003

IEEE Conference on Computational Complexity, Aarhus (Denmark). Program committee member.

2003

Dagstuhl-seminar "Kolmogorov complexity and its appliactions"

2004, 2002

Dagstuhl-seminar "Algebraical methods in quantum and classical computations"

2001

18th International Symposium on Theoretical Aspects of Computer Science, Dresden, Germany. Program Comittee member.

1999

A 3 month research visit to Ecole Normale Supérieure of Lyon, France. Invited by Bruno Durand.

1998

13th Annual IEEE Conference on Computational Complexity, Buffalo, USA.

1998

A 3 month research visit to University of Würzburg, Germany. Invited by Klaus Wagner.

1997/1998

A 6 month research visit to Ecole Normale Supérieure of Lyon, France.

1997

A month research visit to Rutgers University, USA. Invited by Eric Allender.

1997

12th Annual IEEE Conference on Computational Complexity Theory, Ulm, Germany.

1997

A month research visit to the University of Amsterdam. Invited by P. van Emde Boas and P.M.B. Vitányi.

1997

A 10 days research visit to Johannes Gutenberg University, Mainz, Germany. Invited by Clemens Lautemann.

1996

Dagstuhl-seminar "Structure and Complexity"

1995

Third Israel Symposium on Theory of Computing and Systems, Tel-Aviv, Israel, Jan. 1995.

1994

Two weeks research visit to University of Rochester, N.Y. USA. Invited by Lane Hemaspaandra.

1994

COLORET workshop, Amsterdam, the Netherlands

1994

9th Annual IEEE Conference on Structure in Complexity Theory, Amsterdam, the Netherlands

Seminars run

Moscow State University, Faculty of Mechanics and Mathematics

• Kolmogorov Seminar in Complexity of Description and Complexity of Computation (with A.L.Semenov and A.Kh.Shen), 1984--, graduate.
• Pro seminar in Mathematical Logic and Algorithmic Theory (with V.A.Uspensky, A.L.Semenov, A.Kh.Shen, A.A.Razborov), 1984--, undergraduate.

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. V.A. Uspensky, N.K. Vereshchagin, V.E. Plisko. An Introduction to Mathematical Logic. Moscow University Press, 1991, Nauka, 2004, 136 pp. (Russian)

Chapter in book

• N. Vereshchagin. Relativizability in Complexity Theory. Chapter in book L.D. Beklemishev, M. Pentus, and N. Vereshchagin, Provability, Complexity, Grammars, AMS Translations, Series 2, v. 192, 1999, pp. 87--172.

Refereed journal publications

1. N. Vereshchagin and P. Vitányi. "Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection" IEEE Transactions on Information Theory 50:12 (2004) 3265-3290. Preliminary version: Proc. 47th IEEE Symp. Found. Comput. Sci., 2002, 751--760.
2. B. Durand, N. Vereshchagin. "Kolmogorov-Loveland stochasticity for finite strings". Information Processing Letters, 91 (2004) 263-269.
3. O. Mitina and N. Vereshchagin. "How to Use Several Noisy Channels with Unknown Error Probabilities" Information and Computation 182 (2003) 229-241. Preliminary version appeared under the title "How to use expert advice in the case when actual values of estimated events remain unknown." Proc. Eighth Annual Conference on Computational Learning Theory (July 5th--8th), 1995, Santa Cruz, California, 91--97.
4. N.K. Vereshchagin, D.P. Skvortsov, E.Z. Skvortsova, A.V. Chernov. Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. Proceedings of Steklov Institute of Mathematics 242 (2003) 67-85. Preliminary version appeared in: Proceedings of Computer Science Logic'02, Lecture Notes in Computer Science, 2002, v. 2471, pp. 74--88.
5. B. Durand, V. Kanovei, V. Uspensky, N. Vereshchagin. "Do stronger definitions of randomness exist?" Theoretical Computer Science 290:3 (2003) 1987-1996.
6. K. Makarychev, Yu. Makarychev, A. Romashchenko, N. Vereshchagin. "A New class of non Shannon type inequalities for entropies Communications in Information and Systems, 2:2 (2002) 147-166.
7. N. Vereshchagin. "Kolmogorov complexity conditional to large integers". Theoretical Computer Science 271 (2002) 59--67.
8. N. Vereshchagin and M. Vyugin. "Independent minimum length programs to translate between given strings". Theoretical Computer Science 271 (2002) 131--143. Preliminary version in: Proc. of 15th Annual IEEE Conference on Computational Complexity, Florence, July 2000, 138--144.
9. 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.
10. 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.
11. A. Shen and N. Vereshchagin. "Logical operations and Kolmogorov complexity". Theoretical Computer Science 271 (2002) 125--129.
12. 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.
13. R. Raz, G. Tardos, O. Verbitsky, and N. Vereshchagin. "Arthur-Merlin Games in Boolean Decision Trees". Journal of Computer Systems Sciences 59 (1999) 346-372,
14. 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.

Publications in proceedings of selective conferences

1. H. Buhrman, H. Klauck, N. Vereshchagin, P. Vitanyi. "Individual Communication Complexity". 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, Montpelier, France, March 25-27, 2004, Proceedings. Series: Lecture Notes in Computer Science , Vol. 2996, pages 19-30.
2. B.Durand, N.K. Vereshchagin, M.A. Ushakov. " `Ecological' Computations". In: Proc. 31st International Colloquium on Automata, Languages and Programming, ICALP 2004, Turku, Finland, July 12-16, 2004. Series: Lecture Notes in Computer Science , Vol. 3142 Diaz, J.; Karhumaki, J.; Lepista, A.; Sannella, D. (Eds.) pages 457-468.
3. An. Muchnik and N. Vereshchagin. "Logical operations and Kolmogorov complexity II". Proc. of 16th Annual IEEE Conference on Computational Complexity, Chicago, June 2001, 256--265.