Верещагин Николай Константинович
- Профессор:Факультет компьютерных наук / Департамент больших данных и информационного поиска
- Заведующий лабораторией:Факультет компьютерных наук / Департамент больших данных и информационного поиска / Международная лаборатория теоретической информатики
- Начал работать в НИУ ВШЭ в 2013 году.
- Научно-педагогический стаж: 40 лет.
Образование, учёные степени и учёные звания
- 2014Член Европейской академии
- 1997Ученое звание: Профессор
- 1996Доктор физико-математических наук: МГУ им. М.В. Ломоносова, специальность 01.01.06 «Математическая логика, алгебра и теория чисел», тема диссертации: Релятивизуемость в структурной теории сложности вычислений
- 1981
Специалитет: Московский государственный университет им. М.В. Ломоносова, специальность «Математика», квалификация «Математик»
Достижения и поощрения
- Благодарность Высшей школы экономики (декабрь 2022)
- Благодарность Факультета компьютерных наук НИУ ВШЭ (сентябрь 2018)
Надбавка за публикацию в международном рецензируемом научном издании (2021-2022, 2020-2021, 2019-2020, 2017-2018)
Надбавка за статью в зарубежном рецензируемом журнале (2014-2016)
Учебные курсы (2023/2024 уч. год)
- Комбинаторные конструкции в теоретической информатике (Бакалавриат; где читается: Факультет компьютерных наук; 3-й курс, 3, 4 модуль)Рус
- Односторонние функции и их применения (Бакалавриат; где читается: Факультет компьютерных наук; 4-й курс, 1, 2 модуль)Рус
- Теория информации (Маго-лего; 1, 2 модуль)Рус
- Архив учебных курсов
Учебные курсы (2022/2023 уч. год)
- Комбинаторные конструкции в теоретической информатике (Бакалавриат; где читается: Факультет компьютерных наук; 3-й курс, 3, 4 модуль)Рус
- Комбинаторные конструкции в теоретической информатике (Магистратура; где читается: Факультет компьютерных наук; 1-й курс, 3, 4 модуль)Рус
- Односторонние функции и их применения (Бакалавриат; где читается: Факультет компьютерных наук; 4-й курс, 1, 2 модуль)Рус
Учебные курсы (2021/2022 уч. год)
- Комбинаторные конструкции в теоретической информатике (Бакалавриат; где читается: Факультет компьютерных наук; 3-й курс, 3, 4 модуль)Рус
- Односторонние функции и их применения (Бакалавриат; где читается: Факультет компьютерных наук; 4-й курс, 1, 2 модуль)Рус
Учебные курсы (2020/2021 уч. год)
- Дискретная математика 2 (углубленный курс) (Бакалавриат; где читается: Факультет компьютерных наук; 2-й курс, 1, 2 модуль)Рус
- Комбинаторные конструкции в теоретической информатике (Бакалавриат; где читается: Факультет компьютерных наук; 3-й курс, 3, 4 модуль)Рус
- Теория информации (Бакалавриат; где читается: Факультет компьютерных наук; 4-й курс, 1, 2 модуль)Рус
Учебные курсы (2019/2020 уч. год)
- Дискретная математика 2 (Бакалавриат; где читается: Факультет компьютерных наук; 2-й курс, 1, 2 модуль)Рус
- Математическая логика и сложность вычислений (Бакалавриат; где читается: Факультет компьютерных наук; 3-й курс, 3, 4 модуль)Рус
Учебные курсы (2018/2019 уч. год)
- Дискретная математика - 2 (Бакалавриат; где читается: Факультет компьютерных наук; 2-й курс, 1, 2 модуль)Рус
- Дополнительные главы линейной алгебры (Дисциплина общефакультетского пула; где читается: Факультет компьютерных наук; 3, 4 модуль)Рус
Коды с исправлением ошибок (Аспирантура; где читается: Факультет компьютерных наук; направление "02.06.01. Компьютерные и информационные науки", направление "09.06.01. Информатика и вычислительная техника"; 1-й курс, 1 семестр)Рус
- Математическая логика и сложность вычислений (Бакалавриат; где читается: Факультет компьютерных наук; 3-й курс, 3, 4 модуль)Рус
Учебные курсы (2017/2018 уч. год)
- Дискретная математика 2 (Бакалавриат; где читается: Факультет компьютерных наук; 2-й курс, 1, 2 модуль)Рус
Коды с исправлением ошибок (Аспирантура; где читается: Факультет компьютерных наук; направление "02.06.01. Компьютерные и информационные науки", направление "09.06.01. Информатика и вычислительная техника"; 1-й курс, 1 семестр)Рус
20232
- Статья Vereshchagin N. Information disclosure in the framework of kolmogorov complexity // Theoretical Computer Science. 2023. Vol. 940. P. 108-122. doi
- Статья Верещагин Н. К., Семенов А. Л., Шень А. Последнее открытие Колмогорова? (Колмогоров и алгоритмическая статистика) // Теория вероятностей и ее применения. 2023. Т. 68. № 4. С. 719-750. doi
20222
- Статья Vereshchagin N. A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles // Discrete and Computational Geometry. 2022. Vol. 68. No. 1. P. 188-217. doi
- Глава книги Vereshchagin N. How Much Randomness is Needed to Convert MA Protocols to AM Protocols?, in: Computer Science – Theory and Applications: 17th International Computer Science Symposium in Russia, CSR 2022, Virtual Event, June 29 – July 1, 2022, Proceedings Vol. 13296. Springer, 2022. P. 338-349. doi
20212
- Статья Buhrman H., Christandl M., Koucky M., Lotker Z., Patt-Shamir B., Vereshchagin N. High Entropy Random Selection Protocols // Algorithmica. 2021. Vol. 83. P. 667-694. doi
- Статья Vereshchagin N. Proofs of conservation inequalities for Levin's notion of mutual information of 1974 // Theoretical Computer Science. 2021. Vol. 856. P. 14-20. doi
20203
- Препринт Vereshchagin N. A family of non-periodic tilings of the plane by right golden triangles / Cornell University. Series math "arxiv.org". 2020.
- Статья Vereshchagin N. Descriptive complexity of computable sequences revisited // Theoretical Computer Science. 2020. Vol. 809. P. 531-537. doi
- Статья Durand B., Shen A., Vereshchagin N. On the Structure of Ammann A2 Tilings // Discrete and Computational Geometry. 2020. Vol. 63. P. 577-606. doi
20191
20182
- Статья Romashchenko A., Kaced T., Vereshchagin N. A Conditional Information Inequality and its Combinatorial Applications // IEEE Transactions on Information Theory. 2018. Vol. 64. No. 5. P. 3610-3615. doi
- Статья Vereshchagin N., Bauwens B. F., Makhlin A., Zimand M. Short lists with short programs in short time // Computational Complexity. 2018. Vol. 27. No. 1. P. 31-61. doi
20176
- Статья Vereshchagin N., Shen A. Algorithmic Statistics: Forty Years Later. // Lecture Notes in Computer Science. 2017. Vol. 10010. P. 669-737. doi
- Глава книги Shen A., Vereshchagin N. Algorithmic Statistics: Forty Years Later., in: Computability and Complexity. Berlin : Springer, 2017. doi P. 669-737. doi
- Книга Shen A., Uspensky V. A., Vereshchagin N. Kolmogorov complexity and algorithmic randomness / Пер. с рус. American Mathematical Society, 2017.
- Статья Vereshchagin N. Short lists with short programs from programs of functions and strings // Theory of Computing Systems. 2017. Vol. 61. No. 4. P. 1440-1450. doi
- Глава книги Vereshchagin N., Milovanov A. Stochasticity in Algorithmic Statistics for Polynomial Time, in: 32nd Computational Complexity Conference. Вадерн : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18. doi
- Препринт Vereshchagin N., Milovanov A. Stochasticity in Algorithmic Statistics for Polynomial Time / Weizmann Institute of Science. Series Technical report "Electronic Colloquium on Computational Complexity". 2017. No. TR17-043.
20162
- Статья Vereshchagin N. Algorithmic Minimal Sufficient Statistics: a New Approach // Theory of Computing Systems. 2016. Vol. 58. No. 3. P. 463-481. doi
- Статья Brody J., Buhrman H., Koucký M., Loff B., Speelman F., Vereshchagin N. Towards a Reverse Newman’s Theorem in Interactive Information Complexity // Algorithmica. 2016. Vol. 76. No. 3. P. 749-781. doi
20151
20143
- Глава книги Vereshchagin N. Aperiodic Tilings by Right Triangles, in: Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings Vol. 8614. Berlin : Springer, 2014. P. 29-41. doi
- Статья Vereshchagin N. Encoding Invariance in Average Case Complexity // Theory of Computing Systems. 2014. Vol. 54. No. 2. P. 305-317. doi
- Глава книги Vereshchagin N. Randomized communication complexity of approximating Kolmogorov complexity, in: CSR 2014 : 9th International Computer Science Symposium in Russia. Proceedings / Ed. by S. Kuznetsov, J. Pin, E. A. Hirsch. Vol. 8476. Berlin : Springer, 2014. doi P. 365-374. doi
20139
- Глава книги Vereshchagin N. An 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'', in: 8th International Computer Science Symposium in Russia. Berlin : Springer, 2013. P. 203-2011.
- Статья Vereshchagin N. Encoding Invariance in Average Case Complexity // Theory of Computing Systems. 2013
- Глава книги Vereshchagin N. On Algorithmic Strong Sufficient Statistics, in: 9th Conference on Computability in Europe. Berlin : Springer, 2013. P. 424-433.
- Препринт Vereshchagin N. Randomized communication complexity of appropximating Kolmogorov complexity / Hasso-Plattner-Institut. Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178 .
- Препринт Bauwens B., Makhlin A., Vereshchagin N., Zimand M. Short lists with short programs in short time / Hasso-Plattner-Institut. Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-007.
- Препринт Brody J., Buhrman H., Koucky M., Loff B., Speelman F., Vereshchagin N. Towards a Reverse Newman's Theorem in Interactive Information Complexity / Hasso-Plattner-Institut. Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR12-179 .
- Книга Верещагин Н. К., Успенский В. А., Шень А. Колмогоровская сложность и алгоритмическая случайность. М. : МЦНМО, 2013.
- Книга Vereshchagin N., Shen A. Лекции по математической логике и теории алгоритмов Part 1: Начала теории множеств. Beijing : Higher Education Press Limited Company, 2013.
- Книга Vereshchagin N., Шень А. Лекции по математической логике и теории алгоритмов Part 3: Вычислимые функции. Beijing : International Press, 2013.
20123
- Препринт Durand B., Shen A., Vereshchagin N. Ammann tilings: a classification and an application / Cornell University. Series math "arxiv.org". 2012. No. 2896.
- Препринт Bienvenu L., Muchnik A. A., Shen A., Vereshchagin N. Limit complexities revisited [once more] / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.
20114
- Статья Philip Dawid A., Shafer G., Shen A., de Rooij S., Vereshchagin N., Vovk V. Insuring against lost of evidence in game-theoretic probability // Statistics and Probability Letters. 2011. Vol. 81. No. 1. P. 157-162.
- Статья Muchnik A. A., Vereshchagin N. On joint conditional complexity (Entropy) / Пер. с рус. // Proceedings of the Steklov Institute of Mathematics. 2011. Vol. 274. No. 1. P. 90-104.
- Статья Shafer G., Shen A., Vereshchagin N., Vovk V. Test martingales, Bayes factors, and p-values // Statistical Science. 2011. Vol. 26. No. 1. P. 84-101.
- Статья Верещагин Н. К., Мучник А. А. О совместной условной сложности (энтропии). // Труды Математического института им. В.А. Стеклова РАН. 2011. Т. 274. С. 103-118.
20081
Опыт работы
Московский государственный университет им. М.В. Ломоносова:
Ассистент: 1984 - 1991
Старший преподаватель: 1991 - 1992
Профессор: 1998 - наст. время
Институт новых технологий образования
Вед. научн. сотр. 1992 - 1996
Государственная академия Маймонида
Профессор: 1996 - 1998
ВШЭ:
профессор факультета математики: 2013 -2015
профессор факультета комп. наук: 2015 - наст. время
Яндекс ШАД
профессор: 2007 - наст. время
Русско-французская Лаборатория Понселе в НМУ
Научный сотрудник: 2005 - 2015
Информация*
- Общий стаж: 41 год
- Научно-педагогический стаж: 40 лет
- Преподавательский стаж: 33 года
Основное место работы, должность
Профессор кафедры математической логики и теории алгоритмов мехмата МГУ им. М.В. Ломоносова
12 проектов сотрудников НИУ ВШЭ поддержаны Российским научным фондом
Подведены итоги конкурсов 2023 года по приоритетному направлению деятельности Российского научного фонда «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами». Поддержаны семь проектов сотрудников НИУ ВШЭ, реализовать которые предстоит в 2023–2025 годах, с плановым объемом финансирования от 15 до 21 млн рублей. Срок реализации еще пяти проектов продлен на 2023–2024 годы, их финансирование составит от 12 до 14 млн рублей.
Ученые ФКН получили 2 гранта Российского научного фонда
Российский научный фонд подвел итоги четырех конкурсов 2020 года, среди победителей есть представители факультета компьютерных наук Высшей школы экономики.
Ученые ВШЭ получили 15 грантов Российского научного фонда
Российский научный фонд подвел итоги четырех конкурсов 2020 года, среди победителей есть представители Высшей школы экономики. Им присуждены гранты от 12 до 24 млн рублей на срок от 2 до 4 лет.
Александр Шень стал ассоциированным сотрудником международной лаборатории теоретической информатики
Ведущий исследователь Национального центра научных исследований Франции (Directeur de Recherche, CNRS) Александр Шень стал ассоциированным сотрудником международной лаборатории теоретической информатики.
Юбилей Николая Константиновича Верещагина
27 октября юбилей Николая Верещагина, заведующего Международной лабораторией теоретической информатики.
Теоретическая информатика на ФКН
Этим летом в Вышке прошла 13-ая Международная конференция CSR-2018. Одним из ее главных организаторов стала Международная лаборатория теоретической информатики ФКН ВШЭ. Далее в статье – подробнее о некоторых ведущих ученых, которых будет интересно почитать и посмотреть, а также о возможностях на факультете для тех, кто хочет выбрать теоретическую информатику в качестве специализации на 3 курсе или просто интересуется исследованиями в этой области.
HSE and University of London: Joint BA Programme in Applied Data Analysis
In 2018, the Higher School of Economics will launch an English-taught double degree programme in partnership with the University of London in Applied Data Analysis. Graduates will be awarded an undergraduate degree from HSE in Applied Mathematics and Information Science and a Bachelor of Science in Data Science and Business Analytics from the University of London. International applicants are invited to apply online starting November 15, 2017.
НИУ ВШЭ и Лондонский университет открывают бакалаврскую программу двух дипломов по прикладному анализу данных
В 2018 году Высшая школа экономики начинает прием на англоязычную программу бакалавриата «Программа двух дипломов НИУ ВШЭ и Лондонского университета «Прикладной анализ данных». Все, успешно закончившие программу, получат диплом бакалавра по направлению «Прикладная математика и информатика» НИУ ВШЭ и диплом Bachelor of Sciences in Data Science and Business Analytics Лондонского университета.
Computer Science Faculty Staff Attend Symposium in Russia
On June 9-13, the international conference ‘Computer Science Symposium in Russia 2016’ was held in St. Petersburg as part of the Special Semester on Computational and Proof Complexity.
Сотрудники факультета на конференции Computer Science Symposium in Russia 2016
13 июня завершилась международная конференция Computer Science Symposium in Russia 2016, которая проходила 9-13 июня в Санкт-Петербурге во время “Специального семестра по теории сложности”. Семестр начался в апреле и продлится до конца июня. Помимо CSR-2016, в рамках Семестра прошли Symposium on Experimental Algorithms 2016, несколько семинаров, тьюториалов и три воркшопа. Семестр организован сотрудниками Исследовательской лаборатории им. П.Л. Чебышева, также в числе организаторов и участников – такие известные специалисты по Computer Science как Johan Håstad, Jan Krajíček, Pavel Pudlák, Madhu Sudan, Ryan Williams и другие. Сотрудники Международной лаборатории теоретической информатики факультета компьютерных наук принимают активное участие в работе Семестра.
На факультете компьютерных наук создана международная лаборатория теоретической информатики
В 2016 году на факультете компьютерных наук начинает работу новое научно-исследовательское подразделение департамента больших данных и информационного поиска — лаборатория теоретической информатики. Одна из целей лаборатории — интеграция российской школы по теоретической информатике в международное сообщество.
CSR 2015
13-17 июля прошла 10-я международная конференция CSR 2015 – Computer Science in Russia. Эта крупнейшая в России конференция по теоретической информатике была организована при поддержке Иркутского государственного университета, НИУ ВШЭ и компании «Яндекс». В качестве приглашенного докладчика в конференции принял участие доцент Владимир Подольский. Также с докладом выступил доцент Максим Бабенко.