Vladimir V. Podolskii

According to our database, Vladimir V. Podolskii authored at least 44 papers between 2008 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2023

One-Way Communication Complexity of Partial XOR Functions.

Vladimir V. Podolskii, Dmitrii Sluch

Electron. Colloquium Comput. Complex., 2023

Towards Simpler Sorting Networks and Monotone Circuits for Majority.

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2023

Logical Languages Accepted by Transformer Encoders with Hard Attention.

Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii

CoRR, 2023

2022

Multiparty Karchmer-Wigderson Games and Threshold Circuits.

Alexander Kozachinskiy, Vladimir V. Podolskii

Theory Comput., 2022

On the Decision Tree Complexity of Threshold Functions.

Anastasiya Chistopolskaya, Vladimir V. Podolskii

Theory Comput. Syst., 2022

Constant-Depth Sorting Networks.

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2022

A tetrachotomy of ontology-mediated queries with a covering axiom.

Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev

Artif. Intell., 2022

Polynomial Threshold Functions for Decision Lists.

Vladimir V. Podolskii, Nikolay V. Proskurin

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

Deciding Boundedness of Monadic Sirups.

Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

2020

CSR 2018 Special Issue on TOCS.

Fedor V. Fomin, Vladimir V. Podolskii

Theory Comput. Syst., 2020

Tropical Combinatorial Nullstellensatz and Sparse Polynomials.

Dima Grigoriev, Vladimir V. Podolskii

Found. Comput. Math., 2020

A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom.

Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, 2020

2019

Complexity of Linear Operators.

Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2019

2018

Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity.

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

J. ACM, 2018

Parity Decision Tree Complexity is Greater Than Granularity.

Anastasiya Chistopolskaya, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2018

Tropical Effective Primary and Dual Nullstellensätze.

Dima Grigoriev, Vladimir V. Podolskii

Discret. Comput. Geom., 2018

2017

Bounds in Ontology-Based Data Access via Circuit Complexity.

Vladimir V. Podolskii

Theory Comput. Syst., 2017

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties.

Vladimir V. Podolskii, Alexander A. Sherstov

Electron. Colloquium Comput. Complex., 2017

The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries.

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Vladislav Ryzhikov, Michael Zakharyaschev

Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom.

Olga Gerasimova, Stanislav Kikot, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the Knowledge Engineering and Semantic Web - 8th International Conference, 2017

Tropical Combinatorial Nullstellensatz and Fewnomials Testing.

Dima Grigoriev, Vladimir V. Podolskii

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom.

Olga Gerasimova, Stanislav Kikot, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the 30th International Workshop on Description Logics, 2017

2016

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates.

Alexander S. Kulikov, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2016

Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries.

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the 29th International Workshop on Description Logics, 2016

2015

Complexity of Tropical and Min-plus Linear Prevarieties.

Dima Grigoriev, Vladimir V. Podolskii

Comput. Complex., 2015

Tropical Effective Primary and Dual Nullstellens"atze.

Dima Grigoriev, Vladimir V. Podolskii

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results.

Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Combined Complexity of Answering Tree-like Queries in OWL 2 QL.

Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii

Proceedings of the 28th International Workshop on Description Logics, 2015

Circuit Complexity Meets Ontology-Based Data Access.

Vladimir V. Podolskii

Proceedings of the Computer Science - Theory and Applications, 2015

2014

On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases.

Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

CoRR, 2014

The price of query rewriting in ontology-based data access.

Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev

Artif. Intell., 2014

Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries.

Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii

Proceedings of the Informal Proceedings of the 27th International Workshop on Description Logics, 2014

On the succinctness of query rewriting over shallow ontologies.

Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

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), 2014

2013

Polynomial threshold functions and Boolean threshold circuits.

Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2013

Patience of matrix games.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas

Discret. Appl. Math., 2013

Lower Bound on Weights of Large Degree Threshold Functions

Vladimir V. Podolskii

Log. Methods Comput. Sci., 2013

Query Rewriting over Shallow Ontologies.

Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the Informal Proceedings of the 26th International Workshop on Description Logics, Ulm, Germany, July 23, 2013

2012

Exponential lower bound for bounded depth circuits with few threshold gates.

Vladimir V. Podolskii

Inf. Process. Lett., 2012

Exponential Lower Bounds and Separation for Query Rewriting.

Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Long Rewritings, Short Rewritings.

Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev

Proceedings of the 2012 International Workshop on Description Logics, 2012

2010

Weights of Exact Threshold Functions.

László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Exact Threshold Circuits.

Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Perceptrons of large weight.

Vladimir V. Podolskii

Probl. Inf. Transm., 2009

2008

A Uniform Lower Bound on Weights of Perceptrons.

Vladimir V. Podolskii

Proceedings of the Computer Science, 2008