Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/lifr/pers/ver.htm
Дата изменения: Wed Oct 4 13:56:50 2006
Дата индексирования: Tue Oct 2 01:45:48 2012
Кодировка:
Поисковые слова: р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п п р п п р п п р п

Labo J.-V.Poncelet: N.Vereshchagin

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

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)
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

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.
B. Durand, N. Vereshchagin. "Kolmogorov-Loveland stochasticity for finite strings". Information Processing Letters, 91 (2004) 263-269.
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.
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.
B. Durand, V. Kanovei, V. Uspensky, N. Vereshchagin. "Do stronger definitions of randomness exist?" Theoretical Computer Science 290:3 (2003) 1987-1996.
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.
N. Vereshchagin. "Kolmogorov complexity conditional to large integers". Theoretical Computer Science 271 (2002) 59--67.
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.
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.
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.
A. Shen and N. Vereshchagin. "Logical operations and Kolmogorov complexity". Theoretical Computer Science 271 (2002) 125--129.
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.
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,
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

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.
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.
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.