Vladimir V. Podolskii

Publications²¹

• 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.