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