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
- 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
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 (2019/2020)
- A Theorist's Toolkit (Master’s programme; Faculty of Computer Science; 1 year, 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; 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
- Past Courses
Courses (2018/2019)
- Additional Chapters of Linear Algebra (Optional course (faculty); Faculty of Computer Science; 3, 4 module)Rus
- A Theorist's Toolkit (Bachelor’s programme; Faculty of Computer Science; 4 year, 3 module)Eng
- 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" (Bachelor’s programme; Faculty of Computer Science; 3 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; 4 year, 1, 2 module)Eng
- 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
- Research Seminar "Theoretical Informatics" (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 (2016/2017)
- Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
- Discrete Mathematics 2 (Bachelor’s programme; Faculty of Computer Science; 2 year, 1, 2 module)Rus
- Research seminar "Theoretical informatics" (Bachelor’s programme; Faculty of Computer Science; 3 year, 1-4 module)Rus
Courses (2015/2016)
- Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; 1 year, 1-3 module)Rus
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; 2 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
Courses (2014/2015)
- Algebra (Bachelor’s programme; Faculty of Computer Science; 1 year, 4 module)Rus
Discrete Mathematics (Bachelor’s programme; Faculty of Computer Science; field of study "01.03.02. Прикладная математика и информатика", field of study "01.03.02. Прикладная математика и информатика"; 1 year, 1-3 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
Publications21
- 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.
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.
