Nikolay Vereshchagin
- Professor:Faculty of Computer Science / Big Data and Information Retrieval School
- Laboratory Head:Faculty of Computer Science / Big Data and Information Retrieval School / Laboratory of Theoretical Computer Science
- Nikolay Vereshchagin has been at HSE University since 2013.
Education, Degrees and Academic Titles
- 2014Member of the Academy of Europe
- 1997Professor
- 1996
Doctor of Sciences* in Mathematical Logic, Algebra and Number Theory
Lomonosov Moscow State University - 1981
Degree
Lomonosov Moscow State University
A post-doctoral degree called Doctor of Sciences is given to reflect second advanced research qualifications or higher doctorates in ISCED 2011.
Courses (2023/2024)
- Combinatorial Сonstructions in Theoretical Computer Science (Bachelor’s programme; Faculty of Computer Science; 3 year, 3, 4 module)Rus
- Combinatorial Сonstructions in Theoretical Computer Science (Master’s programme; Faculty of Computer Science; 1 year, 3, 4 module)Rus
- Information Theory (Mago-Lego; 1, 2 module)Rus
- Information Theory (Master’s programme; Faculty of Computer Science; 1 year, 1, 2 module)Rus
- One-Way Functions and Their Applications (Bachelor’s programme; Faculty of Computer Science; 4 year, 1, 2 module)Rus
- Past Courses
Courses (2022/2023)
- Combinatorial Сonstructions in Theoretical Computer Science (Bachelor’s programme; Faculty of Computer Science; 3 year, 3, 4 module)Rus
- Combinatorial Сonstructions in Theoretical Computer Science (Master’s programme; Faculty of Computer Science; 1 year, 3, 4 module)Rus
- One-Way Functions and Their Applications (Bachelor’s programme; Faculty of Computer Science; 4 year, 1, 2 module)Rus
Courses (2021/2022)
- Combinatorial Сonstructions in Theoretical Computer Science (Bachelor’s programme; Faculty of Computer Science; 3 year, 3, 4 module)Rus
- One-Way Functions and Their Applications (Bachelor’s programme; Faculty of Computer Science; 4 year, 1, 2 module)Rus
Courses (2020/2021)
- Combinatorial Сonstructions in Theoretical Computer Science (Bachelor’s programme; Faculty of Computer Science; 3 year, 3, 4 module)Rus
- Discrete Mathematics 2 (Bachelor’s programme; Faculty of Computer Science; 2 year, 1, 2 module)Rus
- Information Theory (Bachelor’s programme; Faculty of Computer Science; 4 year, 1, 2 module)Rus
Conferences
- 201732nd Computational Complexity Conference (Рига). Presentation: Stochasticity in Algorithmic Statistics for Polynomial Time
- 20138th International Computer Science Symposium in Russia (Санкт-Петербург). Presentation: 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''
- Eighth International Conference on Computability, Complexity and Randomness (Москва). Presentation: Total and plain conditional complexities
20231
20222
- Article 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
- Chapter 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
- Article 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
- Article 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
- Preprint Vereshchagin N. A family of non-periodic tilings of the plane by right golden triangles / Cornell University. Series math "arxiv.org". 2020.
- Article Vereshchagin N. Descriptive complexity of computable sequences revisited // Theoretical Computer Science. 2020. Vol. 809. P. 531-537. doi
- Article 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
- Article 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
- Article 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
- Article Vereshchagin N., Shen A. Algorithmic Statistics: Forty Years Later. // Lecture Notes in Computer Science. 2017. Vol. 10010. P. 669-737. doi
- Chapter Shen A., Vereshchagin N. Algorithmic Statistics: Forty Years Later., in: Computability and Complexity. Berlin : Springer, 2017. doi P. 669-737. doi
- Book Shen A., Uspensky V. A., Vereshchagin N. Kolmogorov complexity and algorithmic randomness / Пер. с рус. American Mathematical Society, 2017.
- Article 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
- Chapter 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
- Preprint 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
- Article Vereshchagin N. Algorithmic Minimal Sufficient Statistics: a New Approach // Theory of Computing Systems. 2016. Vol. 58. No. 3. P. 463-481. doi
- Article 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
- Chapter 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
- Article Vereshchagin N. Encoding Invariance in Average Case Complexity // Theory of Computing Systems. 2014. Vol. 54. No. 2. P. 305-317. doi
- Chapter 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
20136
- Chapter 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.
- Article Vereshchagin N. Encoding Invariance in Average Case Complexity // Theory of Computing Systems. 2013
- Chapter Vereshchagin N. On Algorithmic Strong Sufficient Statistics, in: 9th Conference on Computability in Europe. Berlin : Springer, 2013. P. 424-433.
- Preprint Vereshchagin N. Randomized communication complexity of appropximating Kolmogorov complexity / Hasso-Plattner-Institut. Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178 .
- Preprint 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.
- Preprint 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 .
20122
- Preprint Durand B., Shen A., Vereshchagin N. Ammann tilings: a classification and an application / Cornell University. Series math "arxiv.org". 2012. No. 2896.
- Preprint Bienvenu L., Muchnik A. A., Shen A., Vereshchagin N. Limit complexities revisited [once more] / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.
20113
- Article 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.
- Article 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.
- Article 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.
Employment history
Affiliations
• Moscow State University, Faculty of Mechanics and Mathematics. Assistant
10/19848/1991, Senior lecturer, 9/19911/1992. Associate Professor
(half-time) 2/19928/1997. Professor, 9/1998.
• Higher School of Economics, Professor, Dept. of Mathematics, 10/2013
8/2014, Dept. of Computer Science, 9/2015.
• Yandex, School od Data Analysis, Professor, 9/2007.
• Poncelet Lab at Moscow Independent University, 01/2005 -12/2015.
• Institute of New Technologies in Education. Head scientist, 2/1992
9/1996.
• Maimonid State academy, Professor, 10/19968/1998.
Main affiliation
Moscow State University, Dept. of Mathematical Logic and Theory of Algorithms, Professor
HSE University Researchers Receive Fifteen Grants from the Russian Science Foundation
The Russian Science Foundation has announced the winners of four 2020 competitions. Some of the winners are from HSE University. They have received grants of 12 to 24 million roubles, for a term of two to four years.
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.
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.
Faculty of Computer Science to Launch New Theoretical Computer Science Lab
This year, the HSE Faculty of Computer Science is opening an international theoretical computer science laboratory, which will be the new research division of the Big Data and Information Retrieval School. One of the lab’s main objectives is to help bring the Russian school of theoretical computer science to the world stage.
10th International Computer Science Symposium in Russia
On July 13th-17th 2015, the 10th International Computer Science Symposium in Russia took place. The largest conference on theoretical informatics in Russia was organized by Irkutsk State University, the Higher School of Economics and Yandex. Vladimir Podolskii, Associate Professor at the Big Data and Information Retrieval School took part in the event as guest speaker. Maxim Babenko, Head of the Joint Department with Yandex also delivered a report during the event.