Vladimir Podolskii

According to our database, Vladimir Podolskii authored at least 48 papers between 2007 and 2025.

Collaborative distances:

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

2025

Communication Complexity of Equality and Error Correcting Codes.

Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2025

Nearest Neighbor Complexity and Boolean Circuits.

Mason DiCicco, Vladimir Podolskii, Daniel Reichman

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity.

Vladimir Podolskii, Alexander Shekhovtsov

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Complexity Aspects of the Extension of Wagner's Hierarchy to <i>k</i>-Partitions.

Vladimir Podolskii, Victor Selivanov

Proceedings of the Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024), 2024

Logical Languages Accepted by Transformer Encoders with Hard Attention.

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

Proceedings of the Twelfth International Conference on Learning Representations, 2024

One-Way Communication Complexity of Partial XOR Functions.

Vladimir V. Podolskii, Dmitrii Sluch

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Towards Simpler Sorting Networks and Monotone Circuits for Majority.

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

Proceedings of the Approximation, 2024

2023

Constant-Depth Sorting Networks.

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

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

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

On the Decision Tree Complexity of Threshold Functions.

Anastasiya Chistopolskaya, Vladimir V. Podolskii

Proceedings of the Computer Science - Theory and Applications, 2020

Multiparty Karchmer - Wigderson Games and Threshold Circuits.

Alexander Kozachinskiy, Vladimir V. Podolskii

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Complexity of Linear Operators.

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

Proceedings of the 30th International Symposium on Algorithms and Computation, 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

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

Alexander S. Kulikov, Vladimir V. Podolskii

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 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

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

Patience of matrix games.

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

Discret. Appl. Math., 2013

Polynomial Threshold Functions and Boolean Threshold Circuits.

Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii

Proceedings of the Mathematical Foundations of Computer Science 2013, 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

Lower Bound on Weights of Large Degree Threshold Functions.

Vladimir V. Podolskii

Proceedings of the How the World Computes, 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

2008

A Uniform Lower Bound on Weights of Perceptrons.

Vladimir V. Podolskii

Proceedings of the Computer Science, 2008

2007

Perceptrons of Large Weight.

Vladimir V. Podolskii

Proceedings of the Computer Science, 2007