Vladimir V. Podolskii
- Head, Associate Professor:Faculty of Computer Science / Big Data and Information Retrieval School
- Senior Research Fellow:Faculty of Computer Science / Big Data and Information Retrieval School / Laboratory of Theoretical Computer Science
- Programme Academic Supervisor:Master of Data Science
- Member of the HSE Academic Council
- Vladimir V. Podolskii has been at HSE University since 2014.
Education and Degrees
- 2009
Candidate of Sciences* (PhD) in Mathematical Logic, Algebra and Number Theory
Lomonosov Moscow State University - 2009
Doctoral programme in Algebra, logic and number theory
Lomonosov Moscow State University, Mathematical Logic and Theory of Algorithms - 2006
Degree in Mathematics
Lomonosov Moscow State University, Mathematical Logic and Theory of Algorithms
According to the International Standard Classification of Education (ISCED) 2011, Candidate of Sciences belongs to ISCED level 8 - "doctoral or equivalent", together with PhD, DPhil, D.Lit, D.Sc, LL.D, Doctorate or similar. Candidate of Sciences allows its holders to reach the level of the Associate Professor.
Student Term / Thesis Papers
- Bachelor
E. Kryukova, Representation of Boolean Functions by Polynomials. Faculty of Computer Science, 2020
Y. Ivanashev, Representation of Boolean Functions by Polynomials. Faculty of Computer Science, 2020
M. Filimonov, Boolean Function Complexity. Faculty of Computer Science, 2020
A. Shikhova, Decision Trees and Related Complexity Measures for Boolean Functions. Faculty of Computer Science, 2019
A. Storozhenko, Communication Complexity and its Applications. Faculty of Computer Science, 2019
G. Posobin, Changing Kolmogorov Complexity with Random Noise. Faculty of Computer Science, 2018
Courses (2020/2021)
- A Theorist's Toolkit (Bachelor’s programme; Faculty of Computer Science; 4 year, 3 module)Eng
- A Theorist's Toolkit (Master’s programme; Faculty of Computer Science; 1 year, 3 module)Rus
- Discrete Mathematic (Additional Chapters) 1 (Optional course (faculty); Faculty of Computer Science; 1, 2 module)Rus
- Discrete Mathematic (Additional Chapters) 2 (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
- Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
- Research Seminar "Theoretical Informatics" (Bachelor’s programme; Faculty of Computer Science; 3 year, 1-4 module)Rus
- Research Seminar "Theoretical Informatics" (Master’s programme; Faculty of Computer Science; 2 year, 1, 2 module)Rus
- Research Seminar "Theoretical Informatics" (Master’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
- Research seminar "Theoretical informatics 2" (Bachelor’s programme; Faculty of Computer Science; 4 year, 1-3 module)Rus
- Statistical Learning Theory (Bachelor’s programme; Faculty of Computer Science; 4 year, 1, 2 module)Eng
- Statistical Learning Theory (Bachelor’s programme; Faculty of Computer Science; 3 year, 1, 2 module)Eng
- Statistical Learning Theory (Master’s programme; Faculty of Computer Science; 2 year, 1, 2 module)Eng
- Past Courses
Courses (2019/2020)
- A Theorist's Toolkit (Master’s programme; Faculty of Computer Science; 1 year, 3, 4 module)Rus
- Discrete Mathematic (Additional Chapters) 1 (Optional course (faculty); Faculty of Computer Science; 1, 2 module)Rus
- Discrete Mathematic (Additional Chapters) 2 (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
- Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
- Introductory Research Seminar (Bachelor’s programme; Faculty of Computer Science; 2 year, 3 module)Rus
- Research Seminar "Theoretical Informatics" (Bachelor’s programme; Faculty of Computer Science; 3 year, 1-4 module)Rus
- Research Seminar "Theoretical Informatics" (Master’s programme; Faculty of Computer Science; 1 year, 1-4 module)Rus
- Research seminar "Theoretical informatics 2" (Bachelor’s programme; Faculty of Computer Science; 4 year, 1-3 module)Rus
- Theory of Computation (Bachelor’s programme; Faculty of Computer Science; 3 year, 1, 2 module)Eng
- Theory of Computation (Master’s programme; Faculty of Computer Science; 1 year, 1, 2 module)Eng
Courses (2018/2019)
- Additional Chapters of Linear Algebra (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
- Discrete Mathematic (Additional Chapters) 1 (Optional course (faculty); Faculty of Computer Science; 1, 2 module)Rus
- Discrete Mathematic (Additional Chapters) 2 (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
- Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
- Introductory Research Seminar (Bachelor’s programme; Faculty of Computer Science; 2 year, 3 module)Eng
- Research seminar "Theoretical informatics 1" (Bachelor’s programme; Faculty of Computer Science; 3 year, 1-4 module)Rus
- Theory of Computation (Bachelor’s programme; Faculty of Computer Science; 3 year, 1, 2 module)Eng
Courses (2017/2018)
- Discrete Mathematic (Additional Chapters) (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
- Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
- Introductory Research Seminar (Bachelor’s programme; Faculty of Computer Science; 2 year, 3 module)Eng
Courses (2015/2016)
Research Seminar "Theoretical Informatics, Computational Logic and Artificial Intelligence" (Bachelor’s programme; Faculty of Computer Science; "Алгоритмика"; field of study "01.03.02. Прикладная математика и информатика"; 3 year, 1-4 module)Rus
- Research Seminar "Theoretical Informatics, Computational Logic and Artificial Intelligence" (Bachelor’s programme; Faculty of Computer Science; 4 year, 1-3 module)Rus
- Research Seminar "Theoretical Informatics, Computational Logic and Artificial Intelligence" (Bachelor’s programme; Faculty of Computer Science; 2 year, 1-4 module)Rus
Conferences
- 201532nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) (Garching). Presentation: Tropical Effective Primary and Dual Nullstellens"atze
- The 10th International Computer Science Symposium in Russia (Listvyanka). Presentation: Circuit Complexity Meets Ontology-Based Data Access
Publications28
- Book Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А., Шень А. Лекции по дискретной математике. М. : Издательский дом НИУ ВШЭ, 2021. doi
- Chapter Gerasimova O., Kikot S., Kurucz A., Podolskii V. V., Zakharyaschev M. A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom, in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning. IJCAI Organization: The International Joint Conference on Artificial Intelligence (IJCAI), 2020. P. 403-413. doi
- Article Podolskii V. V., Sherstov A. A. Inner Product and Set Disjointness: Beyond Logarithmically Many Parties // ACM Transactions on Computation Theory. 2020. Vol. 12. No. 4. P. 26. doi
- Chapter Chistopolskaya A., Podolskii V. V. On the Decision Tree Complexity of Threshold Functions, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings Vol. 12159. Springer, 2020. doi P. 198-210. doi
- Book Special Issue on Computer Science Symposium in Russia / Ed. by Ф. В. Фомин, V. V. Podolskii.; Ed. by Ф. В. Фомин, V. V. Podolskii. Vol. 64. Issue 1. Springer, 2020. doi
- Article Grigoriev D., Podolskii V. V. Tropical Combinatorial Nullstellensatz and Sparse Polynomials // Foundations of Computational Mathematics. 2020. Vol. 20. No. 4. P. 753-781. doi
- Article Podolskii V. V., Kulikov A. S. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates // Theory of Computing Systems. 2019. Vol. 63. No. 5. P. 956-986. doi
- Book Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А., Шень А. Лекции по дискретной математике. Издательский дом НИУ ВШЭ, 2019. (in press)
- Book Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi
- Article Bienvenu M., Kikot S., Kontchakov R., Podolskii V. V., Zakharyaschev M. Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity // Journal of the ACM. 2018. Vol. 65. No. 5. P. 28:1-28:51. doi
- Article Podolskii V. V., Grigoriev D. Tropical Effective Primary and Dual Nullstellensätze // Discrete and Computational Geometry. 2018. Vol. 59. No. 3. P. 507-552. doi
- Chapter Kulikov A., Podolskii V. V. Computing majority by constant depth majority circuits with low fan-in gates, in: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, Germany Т. 66. Лейпциг : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 1-14. doi
- Chapter Gerasimova O., Kikot S., Podolskii V. V., Zakharyaschev M. More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom, in: Proceedings of the 8th international Conference on Knowledge Engineering and Semantic Web. Berlin : Springer, 2017. doi P. 143-158. doi
- Chapter Gerasimova O., Podolskii V. V., Kikot S., Zakharyaschev M. On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom, in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.. Aachen : CEUR Workshop Proceedings, 2017. Ch. 19. P. 1-12.
- Chapter Podolskii V. V., Zakharyaschev M., Bienvenu M., Kikot S., Ryzhikov V., Kontchakov R. The complexity of ontology-based data access with OWL2QL and bounded treewidth queries, in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems Part F127745. ACM, 2017. P. 201-216. doi
- Article Podolskii V. V., Grigoriev D. Tropical Combinatorial Nullstellensatz and Fewnomials Testing // Lecture Notes in Computer Science. 2017. Vol. 10472. P. 284-297. doi
- Chapter Bienvenu M., Kikot S., Kontchakov R., Podolskii V. V., Zakharyaschev M. Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries, in: International Workshop on Description Logics, DL 2016 Issue 1577. , 2016. P. 1-13.
- Chapter Bienvenu M., Kikot S., Podolskii V. V. Combined Complexity of Answering Tree-like Queries in OWL 2 QL, in: Description Logics Workshop, Proceedings of the 28th International Workshop on Description Logics, Athens, Greece, June 7th to 10th, 2015. Vol. 1350. CEUR Workshop Proceedings, 2015. P. 1-4.
- Article Grigoriev D., Podolskii V. V. Complexity of Tropical and Min-plus Linear Prevarieties // Computational Complexity. 2015. Vol. 24. No. 1. P. 31-64.
- Article Hansen K. A., Podolskii V. V. Polynomial threshold functions and Boolean threshold circuits // Information and Computation. 2015. Vol. 240. P. 56-73. doi
- Chapter Podolskii V. V., Bienvenu M., Kikot S. Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results, in: Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on. Los Alamitos : IEEE, 2015. P. 317-328. doi
- Chapter Grigoriev D., Podolskii V. V. Tropical Effective Primary and Dual Nullstellens"atze, in: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Leibniz International Proceedings in Informatics (LIPIcs) Vol. 30. Dagstuhl : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2015. P. 379-391.
- Chapter Kikot S., Kontchakov R., Podolskii V. V., Zakharyaschev M. On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase, in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). NY : ACM, 2014. P. 1-10.
- Chapter Bienvenu M., Kikot S., Podolskii V. V. Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries, in: CEUR Workshop Proceedings Vol. 1193: Informal Proceedings of the 27th International Workshop on Description Logics. Vienna, Austria, July 17-20, 2014. Wien : CEUR Workshop Proceedings, 2014. P. 45-57.
- Article Gottlob G., Kikot S., Kontchakov R., Podolskii V. V., Schwentick T., Zakharyaschev M. The Price of Query Rewriting in Ontology-Based Data Access // Artificial Intelligence. 2014. Vol. 213. P. 42-59.
- Article Podolskii V. V. Lower bound on weights of large degree threshold functions // Logical Methods in Computer Science. 2013. Vol. 9. No. 2. P. 1-17.
- Article Podolskii V. V., Hansen K. A., Ibsen-Jensen R., Tsigaridas E. P. Patience of matrix games // Discrete Applied Mathematics. 2013. Vol. 161. No. 16-17. P. 2440-2459.
- Article Hansen K. A., Podolskii V. V. Polynomial threshold functions and Boolean threshold circuits // Lecture Notes in Computer Science. 2013. Vol. 8087. P. 516-527.
‘Borders Between Countries Are Becoming Blurred Thanks to Online Communication’
Professor Oleg Melnikov is among the international professors invited to work remotely with HSE University’s students this academic year. He lives in California, runs the Data Science department at a company in Palo Alto, and teaches at Stanford and other universities in the United States. At HSE University he teaches a course on machine learning for the students of the Faculty of Computer Science and the International College of Economics and Finance (ICEF), as well as a university-wide optional course, ‘Machine Learning in Python’. He spoke about his work in an interview with the HSE News Service.
‘It’s Cool to See So Many International Participants from Different Backgrounds’
The students of the second cohort in HSE University’s Master of Data Science have started their classes. This English-taught programme is offered entirely online on Coursera and is the first of its kind in Russia.
‘I Was Always a Fan of Online Studying’
Students of the first cohort of the HSE’s online Master of Data Science are now completing their first semester. Offered entirely online on Coursera, the programme attracts students from all over the world. HSE News Service spoke with two international students about what drew them to the programme, the courses they have taken so far, and what their online student community is like.
‘Choosing an Online Degree by HSE University Was a Very Easy Decision to Make’
The classes in the Master of Data Science programme started three months ago. This is the first Master’s degree in Russia offered fully online, with all the courses delivered on Coursera. The students of the first cohort and one of the instructors have shared their impressions.
Students from over 20 Countries Begin Courses in HSE Online Master’s Programme
Classes in the Master of Data Science programme have recently begun. This is the first Master’s programme in Russia taught entirely online on Coursera global educational platform. All classes are conducted in English.
Young Researchers from HSE Receive Awards from the Moscow Government
Vladimir Podolskii, Head of HSE’s Big Data and Information Retrieval School, and Elena Vakulenko, Assistant Professor at the Department of Applied Economics, have both received awards for research in mathematics and labour studies, respectively.
Laboratory of Theoretical Computer Science Researchers Get Grant from RFBR and Royal Society
Researchers from the HSE Laboratory of Theoretical Computer Science have won a competition organized by the Russian Foundation for Basic Research (RFBR) and the Royal Society of London for Improving Natural Knowledge.
HSE Launches Two New Specializations in Computer Science on Coursera
‘Introduction to Discrete Mathematics for Computer Science’ and ‘Advanced Machine Learning’ are English-language specializations, both created with the support of the top Russian IT firm Yandex, while the specialization ‘Introduction to Discrete Mathematics for Computer Science’ was developed with the involvement of the University of California at San Diego.
Conference "Mathematical logic, algebra and computation"
On July 18-19 a conference “Mathematical logic, algebra and computation" was held in Moscow. It was organized by the Steklov Mathematical Institute of Russian Academy of Science. The conference was dedicated to the 85th anniversary of academician S. I. Adian.
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.
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.
Faculty of Computer Science to Offer Courses during HSE Summer University
Computer Science programme of the Summer University provides unique opportunities for students from around the world. The programme covers various topics in Computer Science from purely theoretical to applied and practical. Theoretical side of the programme includes both a detailed introduction to the theory of computations and more advanced topics in Artificial Intelligence and Statistical Diagnosis. Practical aspects of the programme are tightly integrated with theoretical material. Participants of the programme will have an opportunity to apply the new knowledge in their own programming experience, for example, in processing of natural languages, creating a distributed computing system or implementing a compiler for a programming language.
