| The price of query rewriting in ontology-based data access G Gottlob, S Kikot, R Kontchakov, V Podolskii, T Schwentick, ... Artificial Intelligence 213, 42-59, 2014 | 105 | 2014 |
| Exponential lower bounds and separation for query rewriting S Kikot, R Kontchakov, V Podolskii, M Zakharyaschev International Colloquium on Automata, Languages, and Programming, 263-274, 2012 | 45 | 2012 |
| Exact threshold circuits KA Hansen, VV Podolskii 2010 25th Annual IEEE Conference on Computational Complexity, 270-279, 2010 | 44 | 2010 |
| Perceptrons of large weight VV Podolskii Problems of Information Transmission 45 (1), 46-53, 2009 | 32 | 2009 |
| Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity M Bienvenu, S Kikot, R Kontchakov, VV Podolskii, M Zakharyaschev Journal of the ACM (JACM) 65 (5), 1-51, 2018 | 30 | 2018 |
| Tropical effective primary and dual Nullstellensätze D Grigoriev, VV Podolskii Discrete & Computational Geometry 59 (3), 507-552, 2018 | 28 | 2018 |
| Complexity of tropical and min-plus linear prevarieties D Grigoriev, VV Podolskii Computational complexity 24, 31-64, 2015 | 26 | 2015 |
| Polynomial threshold functions and Boolean threshold circuits KA Hansen, VV Podolskii Information and Computation 240, 56-73, 2015 | 26 | 2015 |
| Weights of exact threshold functions L Babai, KA Hansen, VV Podolskii, X Sun International Symposium on Mathematical Foundations of Computer Science, 66-77, 2010 | 24 | 2010 |
| The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries M Bienvenu, S Kikot, R Kontchakov, VV Podolskii, V Ryzhikov, ... Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of …, 2017 | 21 | 2017 |
| Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates AS Kulikov, VV Podolskii arXiv preprint arXiv:1610.02686, 2016 | 21 | 2016 |
| A uniform lower bound on weights of perceptrons V Podolskii Computer Science–Theory and Applications, 261-272, 2008 | 20 | 2008 |
| On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases S Kikot, R Kontchakov, V Podolskii, M Zakharyaschev arXiv preprint arXiv:1401.4420, 2014 | 17* | 2014 |
| Tree-like queries in OWL 2 QL: succinctness and complexity results M Bienvenu, S Kikot, V Podolskii Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer …, 2015 | 15 | 2015 |
| A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom O Gerasimova, S Kikot, A Kurucz, V Podolskii, M Zakharyaschev Proceedings of the Seventeenth International Conference on Principles of …, 2020 | 11 | 2020 |
| Long rewritings, short rewritings S Kikot, R Kontchakov, V Podolskii, M Zakharyaschev Proceedings of the 2012 International Workshop on Description Logics, 2012 | 11 | 2012 |
| Query rewriting over shallow ontologies S Kikot, R Kontchakov, V Podolskii, M Zakharyaschev CEUR-WS, 2013 | 10 | 2013 |
| Logical languages accepted by transformer encoders with hard attention P Barceló, A Kozachinskiy, AW Lin, V Podolskii arXiv preprint arXiv:2310.03817, 2023 | 9 | 2023 |
| On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom G Olga, VV Podolskii, S Kikot, M Zakharyaschev Proceedings of the 30th International Workshop on Description Logics …, 2017 | 9* | 2017 |
| On the data complexity of ontology-mediated queries with a covering axiom O Gerasimova, S Kikot, V Podolskii, M Zakharyaschev Proceedings of the 30th International Workshop on Description Logics, 2017 | 9 | 2017 |
