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

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

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.