Верещагин Николай Константинович
пользователь
доктор физико-математических наук с 1996 года
доктор физико-математических наук
профессор по кафедре с 19 марта 1997 г.
профессор по специальности № 01.01.06
Количество цитирований статей в журналах по данным
Web of Science: 564,
Scopus: 672
РИНЦ:
IstinaResearcherID (IRID): 615231
Деятельность
-
Статьи в журналах
-
Статьи в сборниках
-
-
-
-
-
-
-
-
-
2014
Randomized communication complexity of approximating Kolmogorov complexity
-
Vereshchagin Nikolay
-
в сборнике Computer Science – Theory and Applications, 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER (VAN GODEWIJCKSTRAAT 30, DORDRECHT, NETHERLANDS, 3311GZ), том 8476, с. 365-374
DOI
-
редактор
Верещагин Николай Константинович
-
-
2013
Improving on Gutfreund, Shaltiel, and Ta-Shma's Paper "If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances"
-
Vereshchagin Nikolay K.
-
в сборнике Computer Science – Theory and Applications, 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 7913, с. 203-211
DOI
-
-
2013
On Algorithmic Strong Sufficient Statistics
-
Vereshchagin Nikolay
-
в сборнике The Nature of Computation. Logic, Algorithms, Applications – 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 7921, с. 424-433
DOI
-
-
-
-
-
2010
An Encoding Invariant Version of Polynomial Time Computable Distributions
-
Vereshchagin Nikolay
-
в сборнике Computer Science – Theory and Applications, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 6072, с. 371-383
DOI
-
-
2009
Algorithmic Minimal Sufficient Statistic Revisited
-
Vereshchagin N.
-
в сборнике Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 5635, с. 478-487
DOI
-
-
2009
Kolmogorov Complexity and Model Selection
-
Vereshchagin Nikolay K.
-
в сборнике Computer Science - Theory and Applications, 4th International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings, серия Lecture Notes in Computer Science, место издания Springer Berlin, том 5675, с. 19-24
DOI
-
-
2008
On Game Semantics of the Affine and Intuitionistic Logics
-
Mezhirov Ilya,
Vereshchagin Nikolai K.
-
в сборнике Logic, Language, Information and Computation, 15th International Workshop, WoLLIC 2008, Edinburgh, UK, July 1-4, 2008, Proceedings, серия Lecture Notes in Computer Science, место издания Springer, том 5110, с. 28-42
DOI
-
-
-
-
2007
High Entropy Random Selection Protocols
-
Vereshchagin Nikolai K.,
Buhrman Harry,
Christandl Matthias,
Koucký Michal,
Lotker Zvi,
Patt-Shamir Boaz
-
в сборнике Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, серия Dagstuhl Seminar Proceedings, место издания Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, том 7411
-
-
2007
High entropy random selection protocols
-
Buhrman Harry,
Christandl Matthias,
Koucky Michal,
Lotker Zvi,
Patt-Shamir Boaz,
Vereshchagin Nikolai
-
в сборнике Proceedings of 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 4627, с. 366-379
DOI
-
-
-
-
2006
Non-reducible descriptions for conditional Kolmogorov complexity
-
Muchnik Andrej,
Shen Alexander,
Ustinov Mikhail,
Vereshchagin Nikolai,
Vyugin Michael
-
в сборнике Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006,, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 3959, с. 15-20
DOI
-
-
2006
Shannon Entropy vs. Kolmogorov Complexity
-
Muchnik Andrei,
Vereshchagin Nikolai
-
в сборнике Computer Science – Theory and Applications, 1st International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings, серия Lecture Notes in Computer Science, место издания Springer, том 3967, с. 281-291
DOI
-
-
-
2004
Ecological Turing Machines
-
Durand Bruno,
Muchnik Andrei,
Ushakov Maxim,
Vereshchagin Nikolai
-
в сборнике 31st International Colloquium on Automata, Languages and Programming, ICALP 2004, Turku, Finland, July 12-16, 2004, Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 3142, с. 457-468
DOI
-
-
2004
Individual Communication Complexity: Extended Abstract
-
Buhrman Harry,
Klauck Hartmut,
Vereshchagin Nikolai K.,
Vitányi Paul M.B.
-
в сборнике STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, серия Lecture Notes in Computer Science, место издания Springer, том 2996, с. 19-30
DOI
-
-
-
2002
Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle
-
Chernov Alexey V.,
Skvortsov Dmitrij P.,
Skvortsova Elena Z.,
Vereshchagin Nikolai K.
-
в сборнике Computer Science Logic, 16th International Workshop, CSL 2002, 11th Annual Conference of the EACSL, Edinburgh, Scotland, UK, September 22-25, 2002, Proceedings, серия Lecture Notes in Computer Science, место издания Springer, том 2471, с. 74-88
DOI
-
-
-
-
-
-
1999
Descriptive Complexity of Computable Sequences
-
Durand Bruno,
Shen Alexander,
Vereshchagin Nikolai K.
-
в сборнике STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, серия Lecture Notes in Computer Science, место издания Springer, том 1563, с. 153-162
DOI
-
-
-
1999
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y"
-
Muchnik Andrei A.,
Romashchenko Andrei E.,
Shen Alexander,
Vereshchagin Nikolai K.
-
в сборнике Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, место издания IEEE Computer Society, с. 114-123
DOI
-
-
1998
Arthur-Merlin Games in Boolean Decision Trees
-
Raz Ran,
Tardos Gábor,
Verbitsky Oleg,
Vereshchagin Nikolai K.
-
в сборнике Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998, место издания IEEE Computer Society, с. 58-67
DOI
-
-
1998
Deterministic rational transducers and random sequences
-
Porrot Sylvian,
Dauchet Max,
Durand Bruno,
Vereshchagin Nikolai K.
-
в сборнике Foundations of Software Science and Computation Structure, First International Conference, FoSSaCS'98, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'98, Lisbon, Portugal, March 28 - April 4, 1998, Proceedings, серия Lecture Notes in Computer Science, издательство SPRINGER-VERLAG BERLIN (HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197), том 1378, с. 258-272
DOI
-
-
-
-
-
-
-
1992
Banishing Robust Turing Completeness
-
Hemachandra Lane A.,
Jain Sanjay,
Vereshchagin Nikolai K.
-
в сборнике Logical Foundations of Computer Science - Tver ’92, Second International Symposium, Tver, Russia, July 20-24, 1992, Proceedings, серия Lecture Notes in Computer Science, место издания Springer, том 620, с. 186-197
DOI
-
-
Книги
-
Доклады на конференциях
-
НИРы
-
-
1 января 2021 - 31 декабря 2025
Алгоритмические и семантические вопросы математической логики. 2021-2025
-
Кафедра математической логики и теории алгоритмов
-
Руководитель:
Семенов А.Л.
Ответственные исполнители:
Золин Е.Е.,
Оноприенко А.А.,
Пентус М.Р.
Участники НИР:
Беклемишев Л.Д.,
Белов А.Я.,
Верещагин Н.К.,
Крупский В.Н.,
Кузнецов С.Л.,
Любецкий В.А.,
Плиско В.Е.,
Сорокин А.А.,
Шехтман В.Б.,
Яворская Т.Л.
-
-
-
-
1 января 2016 - 31 декабря 2020
Алгоритмические и семантические вопросы математической логики. 2016-2020
-
Кафедра математической логики и теории алгоритмов
-
Руководители:
Семенов А.Л.,
Успенский В.А.
Ответственные исполнители:
Золин Е.Е.,
Пентус М.Р.
Участники НИР:
Адян С.И.,
Беклемишев Л.Д.,
Верещагин Н.К.,
Крупский В.Н.,
Кузнецов С.Л.,
Любецкий В.А.,
Плиско В.Е.,
Семенов А.Л.,
Сорокин А.А.,
Шехтман В.Б.,
Яворская Т.Л.
-
-
1 января 2012 - 31 декабря 2014
Сложность определений и сложность вычислений
-
Кафедра математической логики и теории алгоритмов
-
Руководитель:
Верещагин Н.К.
Участники НИР:
Андреев М.А.,
Андреев М.А.,
Бабенко М.А.,
Вялый М.Н.,
Колесниченко И.И.,
Махлин А.Ю.,
Мусатов Д.В.,
Подольский В.В.,
Раскин М.А.,
Ромащенко А.Е.,
Румянцев А.Ю.,
Савченко Р.А.,
Шень А.
-
-
Членство в научных обществах
-
Участие в редколлегии сборников
- 2014
Computer Science – Theory and Applications, 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings
-
член редколлегии:
Верещагин Н.К.
-
серия Lecture Notes in Computer Science, том 8476
-
издательство
SPRINGER
(VAN GODEWIJCKSTRAAT 30, DORDRECHT, NETHERLANDS, 3311GZ)
-
-
Участие в программных комитетах конференций
-
Членство в диссертационных советах
-
Руководство диссертациями
-
-
2019
Сравнение коммуникационной, информационной и вопросной сложности
- Кандидатская диссертация по специальности 01.01.06 - Математическая логика, алгебра и теория чисел (физ.-мат. науки)
- Автор:
Козачинский А.Н., МГУ имени М.В. Ломоносова
-
Научный руководитель:
Верещагин Н.К., д.ф.-м.н., д.ф.-м.н., проф., МГУ имени М.В. Ломоносова
-
Защищена в совете
МГУ.011.4(01.17)
МГУ имени М.В. Ломоносова, Механико-математический факультет
-
Организация, в которой выполнялась работа:
МГУ имени М.В. Ломоносова
-
Оппоненты:
Аблаев Фарид Мансурович,
Вялый М.Н.,
Гирш Эдуард Алексеевич
-
-
2017
О нестохастических по Колмогорову словах
- Кандидатская диссертация по специальности 01.01.06 - Математическая логика, алгебра и теория чисел (физ.-мат. науки)
- Автор:
Милованов Алексей Сергеевич, МГУ имени М.В. Ломоносова
-
Научный руководитель:
Николай Константинович Верещагин, д.ф.-м.н., д.ф.-м.н., проф., МГУ имени М.В. Ломоносова
-
Защищена в совете
МГУ.011.4(01.17)
МГУ имени М.В. Ломоносова, Механико-математический факультет
-
Организация, в которой выполнялась работа:
МГУ имени М.В. Ломоносова
-
Оппоненты:
Владимир Вячеславович Вьюгин,
Даниил Владимирович Мусатов,
Борис Яковлевич Рябко
-
-
-
-
-
-
-
-
-
-
-
Руководство дипломными работами
-
Руководство курсовыми работами
-
Авторство учебных курсов
-
Преподавание учебных курсов